题解 | #矩阵中的路径#
矩阵中的路径
https://www.nowcoder.com/practice/2a49359695a544b8939c77358d29b7e6?tpId=265&rp=1&ru=%2Fexam%2Foj%2Fta&qru=%2Fexam%2Foj%2Fta&sourceUrl=%2Fexam%2Foj%2Fta%3FjudgeStatus%3D2%26page%3D1%26pageSize%3D50%26search%3D%26tpId%3D13%26type%3D265&difficulty=&judgeStatus=3&tags=&title=&gioEnter=menu
和岛屿问题很像，递归加回溯。
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param matrix char字符型vector<vector<>>
* @param word string字符串
* @return bool布尔型
*/
bool hasPath(vector<vector<char> >& matrix, string word) {
if (matrix.empty()) {
return false;
}
bool res = false;
std::vector<std::vector<int>> visited(matrix.size(), std::vector<int>(matrix[0].size(), 0));
for (int i = 0; i < matrix.size(); ++i) {
for (int j = 0; j < matrix[0].size(); ++j) {
if (matrix[i][j] == word[0]) {
visited[i][j] = 1;
res |= dfs(matrix, word, visited, i, j, 1);
if (res) {
return res;
}
visited[i][j] = 0;
}
}
}
return false;
}
private:
bool dfs(const std::vector<std::vector<char>> &matrix, const std::string &word, std::vector<std::vector<int>> &visited, int i, int j, int idx) {
if (idx == word.size()) {
return true;
}
bool res = false;
// 上下左右
if (i > 0 && !visited[i - 1][j] && matrix[i - 1][j] == word[idx]) {
visited[i - 1][j] = 1;
res |= dfs(matrix, word, visited, i - 1, j, idx + 1);
visited[i - 1][j] = 0;
}
if (i < matrix.size() - 1 && !visited[i + 1][j] && matrix[i + 1][j] == word[idx]) {
visited[i + 1][j] = 1;
res |= dfs(matrix, word, visited, i + 1, j, idx + 1);
visited[i + 1][j] = 0;
}
if (j > 0 && !visited[i][j - 1] && matrix[i][j - 1] == word[idx]) {
visited[i][j - 1] = 1;
res |= dfs(matrix, word, visited, i, j - 1, idx + 1);
visited[i][j - 1] = 0;
}
if (j < matrix[0].size() - 1 && !visited[i][j + 1] && matrix[i][j + 1] == word[idx]) {
visited[i][j + 1] = 1;
res |= dfs(matrix, word, visited, i, j + 1, idx + 1);
visited[i][j + 1] = 0;
}
return res;
}
};
