单词方阵

题目描述

给一 $n \times n$ 的字母方阵，内可能蕴含多个 yizhong 单词。单词在方阵中是沿着同一方向连续摆放的。摆放可沿着 $8$ 个方向的任一方向，同一单词摆放时不再改变方向，单词与单词之间可以交叉，因此有可能共用字母。输出时，将不是单词的字母用 * 代替，以突出显示单词。

输入格式

第一行输入一个数 $n$ 。 $(7 \le n \le 100)$ 。第二行开始输入 $n \times n$ 的字母矩阵。

输出格式

突出显示单词的 $n \times n$ 矩阵。

样例 #1

样例输入 #1


7
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa

样例输出 #1


*******
*******
*******
*******
*******
*******
*******

样例 #2

样例输入 #2


8
qyizhong
gydthkjy
nwidghji
orbzsfgz
hhgrhwth
zzzzzozo
iwdfrgng
yyyygggg

样例输出 #2


*yizhong
gy******
n*i*****
o**z****
h***h***
z****o**
i*****n*
y******g

cpp
#include <iostream>
#include <vector>
#include <string>

using namespace std;

const int MAXN = 100;
char grid[MAXN][MAXN];
char result[MAXN][MAXN];

// 定义八个方向的偏移量
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

// 检查从 (x, y) 开始，沿着方向 (dir) 是否能形成 "yizhong" 单词
bool checkWord(int x, int y, int dir, int n, const string& word) {
    for (char c : word) {
        if (x < 0 || x >= n || y < 0 || y >= n || grid[x][y] != c) {
            return false;
        }
        x += dx[dir];
        y += dy[dir];
    }
    return true;
}

// 标记 "yizhong" 单词的位置
void markWord(int x, int y, int dir, int n, const string& word) {
    for (char c : word) {
        result[x][y] = c;
        x += dx[dir];
        y += dy[dir];
    }
}

int main() {
    int n;
    cin >> n;
    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> grid[i][j];
            result[i][j] = '*';
        }
    }
    
    string word = "yizhong";
    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int dir = 0; dir < 8; ++dir) {
                if (checkWord(i, j, dir, n, word)) {
                    markWord(i, j, dir, n, word);
                }
            }
        }
    }
    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << result[i][j];
        }
        cout << endl;
    }
    
    return 0;
}

目录