题解 | #矩阵中的路径#
矩阵中的路径
https://www.nowcoder.com/practice/2a49359695a544b8939c77358d29b7e6
#include <vector> class Solution { public: bool dfs(const vector<vector<char>> &matrix, vector<vector<bool>> &flag_vec, const string &word, const int pos_x, const int pos_y, const int pos_cur) { if (pos_cur >= word.size()) return true; if (pos_x < 0 || pos_x >= matrix.size() || pos_y < 0 || pos_y >= matrix[0].size()) return false; if (flag_vec[pos_x][pos_y] == true) return false; if (matrix[pos_x][pos_y] != word[pos_cur]) return false; flag_vec[pos_x][pos_y] = true; bool ret_up = dfs(matrix, flag_vec, word, pos_x - 1, pos_y, pos_cur + 1); bool ret_down = dfs(matrix, flag_vec, word, pos_x + 1, pos_y, pos_cur + 1); bool ret_left = dfs(matrix, flag_vec, word, pos_x, pos_y - 1, pos_cur + 1); bool ret_right = dfs(matrix, flag_vec, word, pos_x, pos_y + 1, pos_cur + 1); flag_vec[pos_x][pos_y] = false; return ret_up || ret_down || ret_left || ret_right; } /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param matrix char字符型vector<vector<>> * @param word string字符串 * @return bool布尔型 */ bool hasPath(vector<vector<char> >& matrix, string word) { // write code here if (matrix.empty() || matrix[0].empty()) return false; vector<vector<bool>> flag_vec(matrix.size(), vector<bool>(matrix[0].size(), false)); for (int i = 0; i < matrix.size(); ++i) { for (int j = 0; j < matrix[0].size(); ++j) { if (matrix[i][j] != word[0]) continue; if (true == dfs(matrix, flag_vec, word, i, j, 0)) return true; } } return false; } };