矩阵中的路径

Desicription

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串”bcced”的路径，但是矩阵中不包含”abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

Solution

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
class Solution {
private:
    vector<vector<bool>> visit;
    vector<vector<int>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    vector<vector<char>> mat;
    unsigned int row;
    unsigned int col;
    string findString;
    bool found = false;
    void onSearch(int x, int y, int index) {
        if(found) {
            return ;
        }
        if(index == findString.size() -1) {
            found = true;
            return ;
        }
        visit[x][y] = true;
        for(int i = 0; i < 4; i++) {
            int dx = x + dir[i][0];
            int dy = y + dir[i][1];
            if(dx < 0 || dx >= row || dy < 0 || dy >= col || mat[dx][dy] != findString[index + 1] || visit[dx][dy]) {
                continue;
            }
            onSearch(dx, dy, index + 1);
        }

    }
public:
    bool hasPath(const char* matrix, int rows, int cols, char* str) {
        findString = str;
        row = static_cast<unsigned int>(rows);
        col = static_cast<unsigned int>(cols);
        mat = vector<vector<char>>(row, vector<char>(col));
        int index = 0;
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                mat[i][j] = matrix[index++];
            }
        }
        visit = vector<vector<bool>>(row, vector<bool>(col, false));
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(found) {
                    break;
                }
                if(mat[i][j] != findString[0]) {
                    continue;
                }
                onSearch(i, j, 0);
                for(int x = 0; x < row; x++) {
                    for(int y = 0; y < col; y++) {
                        visit[x][y] = false;
                    }
                }
            }
            if(found) {
                break;
            }
        }
        return found;
    }
};