剣指offer 11.行列内のパス
11191 ワード
1つのマトリクスに文字列のすべての文字を含むパスがあるかどうかを判断する関数を設計してください.
パスは、マトリクス内の任意の格子から開始できます.各ステップは、マトリクス内で左、右、上、下に1つの格子を移動できます.
1つのパスがマトリクス内の格子を通過した場合、その後この格子に入ることはできません.
注意:入力されたパスは空ではありません. すべての出現した文字はすべて大文字の英語のアルファベットである.
サンプル
dfs入門問題ですね
パスは、マトリクス内の任意の格子から開始できます.各ステップは、マトリクス内で左、右、上、下に1つの格子を移動できます.
1つのパスがマトリクス内の格子を通過した場合、その後この格子に入ることはできません.
注意:
サンプル
matrix=
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
str="BCCE" , return "true"
str="ASAE" , return "false"
dfs入門問題ですね
class Solution {
public:
vector<vector<bool>> visit;
int n, m;
bool hasPath(vector<vector<char>>& board, string word) {
if(board.empty()) return false;
n = board.size(), m = board[0].size();
visit = vector<vector<bool>> (n, vector<bool> (m, false));
for (int i = 0; i < n; i ++)
for (int j = 0; j < m; j ++){
if (board[i][j] == word[0]){
if (dfs(board, word, i, j, 1)) return true;
}
}
return false;
}
bool dfs(vector<vector<char>>& board, string word, int x, int y, int pos){
if (pos == word.size()) return true;
visit[x][y] = true;
int Next[4][2] = {0,1,0,-1,1,0,-1,0};
for (int k = 0; k < 4; ++ k) {
int nx = x + Next[k][0];
int ny = y + Next[k][1];
if (nx>=0 && ny>=0 && nx < n && ny < m && !visit[nx][ny] && board[nx][ny] == word[pos]){
if (dfs(board, word, nx, ny, pos + 1)) return true;
}
}
visit[x][y] = false;
return false;
}
};