P1101 单词方阵——dfs

单词方阵

题目描述

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

输入：
    8                     输出：
    qyizhong              *yizhong
    gydthkjy              gy******
    nwidghji              n*i*****
    orbzsfgz              o**z****
    hhgrhwth              h***h***
    zzzzzozo              z****o**
    iwdfrgng              i*****n*
    yyyygggg              y******g
1
2
3
4
5
6
7
8
9
10

输入格式

第一行输入一个数 $n$。($7\le n\le 100$)。

第二行开始输入 $n\times n$ 的字母矩阵。

输出格式

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

样例 #1

样例输入 #1

7
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
1
2
3
4
5
6
7
8

样例输出 #1

*******
*******
*******
*******
*******
*******
*******
1
2
3
4
5
6
7

样例 #2

样例输入 #2

8
qyizhong
gydthkjy
nwidghji
orbzsfgz
hhgrhwth
zzzzzozo
iwdfrgng
yyyygggg
1
2
3
4
5
6
7
8
9

样例输出 #2

*yizhong
gy******
n*i*****
o**z****
h***h***
z****o**
i*****n*
y******g
1
2
3
4
5
6
7
8

分析

1. 此题细节挺多吧，如果用dfs的话，就不能依赖于往常的模板，非常灵活；
2. 对于单词的起点y，可以向八个方向进行爆搜，由于单词需要是一条线，不能拐弯，所以不需要回溯。从起点 ‘y’ 开始一路向前不改变方向，而不是每个点都要八个方向dfs（单调方向，所以就不能在dfs函数中，每经过一点就8个方向是错的）；所以不能像往前迷宫型dfs，直接dfs中每个点都要搜八个方向；
3. 其次就是递归出口，由于染色（标记某条成功的路径）是在递归出口完成的，惯性u==7的话，也就是单词最后一个字符的下一个字符，会造成在准备dfs u=7的时候，xx,yy就越界了，比如第一行qyizhong，当后7个字符满足后，准备在’g’的后面再去染色，此时yy=n，就越界结束下一个dfs了，导致这个方案没有进行染色；所以u=6的时候，也就是单词的最后一个字符，顺带判断是否匹配，如果匹配直接染色；

#include

using namespace std;

int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
int n;
char a[105][105];
int vis[105][105];//标记染色
vector<pair<int, int>> v;//保存路径
string s = "yizhong";

//direct为当前这条路的方向
void dfs(int u, int x, int y, int direct) {
    //别惯性u==7，因为u=7时候，可能x,y已越界，下一趟dfs都没进来
    if (u == 6 && a[x][y] == s[u]) {
        //搜够了8个字母且都匹配，染色vis
        for (int i = 0; i < v.size(); i++) {
            int xx = v[i].first, yy = v[i].second;
            vis[xx][yy] = 1;
        }
    }
    //不匹配直接return，自然到不了u=6，自然不会染色错误
    if (a[x][y] != s[u]) {
        return;
    }

    int xx = x + dx[direct];
    int yy = y + dy[direct];
    if (xx >= 0 && yy >= 0 && xx < n && yy < n) {
        //把这条路的路径存起来，方便最后走完这条路进行染色
        v.push_back({xx, yy});
        dfs(u + 1, xx, yy, direct);
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> a[i][j];
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (a[i][j] == 'y') {
                //起点开始向八个方向搜，一路向前不改变方向，而不是每个点都要八个方向dfs（单调方向，所以就不能在dfs函数中，每经过一点就8个方向是错的）
                for (int k = 0; k < 8; k++) {
                    v.push_back({i, j});
                    dfs(0, i, j, k);
                    v.clear();
                }
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (vis[i][j])
                cout << a[i][j];
            else
                cout << "*";
        }
        cout << endl;
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67