题解 | #矩阵中的路径#

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型vector<vector<>> 
     * @param word string字符串 
     * @return bool布尔型
     */

    
    bool hasPath(vector<vector<char> >& matrix, string word) {
        // write code here
        bool res = false;   // 开始并没有找到路径，初始化为false
        // for循环遍历每个位置，带着一个标记本子，记录走过位置
        for (int i = 0; i < matrix.size(); ++i) 
        {
            for(int j = 0; j < matrix[0].size(); ++j)
            {
                int w = 0;      // 每次更新一个开始点，都得从word的第一个单词位置开始遍历
                if(matrix[i][j] == word[w])
                {
                    // 找到新的开始点，则重置标记本子，初始化都是没有走过
                    vector<vector<bool>> board(matrix.size(), vector<bool>(matrix[0].size(), false));
                    // std::cout << " matrix "<< i << " " << j <<std::endl;
                    res = dfs(matrix, board, word, i, j, w);
                    if (res) {  
                        break; // 找到路径就退出
                    }
                }
            }
            if (res) {
                break;
            }
        }
        return res;
    }

    // 上下左右找路子，找到就继续往下找，否则return false
    bool dfs(vector<vector<char>>& matrix, vector<vector<bool>>& board, string& word, int i, int j, int w)
    {
        if(i < 0 || i > matrix.size() -1 || j < 0 || j > matrix[0].size()-1 || board[i][j] || matrix[i][j] != word[w])// 越界、已走过或不等于，则终止
        {
            // std::cout << i << " " << j << " " << w << " false "<<std::endl;
            return false;
        }else if(w == word.size() -1)  // 找到word最后一个单词则返回true
        {
            // std::cout << i << " " << j << " " << w << " true "<<std::endl;
            return true;
        }
        // 遍历过，则给board的元素设置为true
        board[i][j] = true;
        // 往上下左右找，找到则为true
        if(dfs(matrix, board, word, i-1, j, w+1)||
            dfs(matrix, board, word, i+1, j, w+1)||
            dfs(matrix, board, word, i, j-1, w+1)||
            dfs(matrix, board, word, i, j+1, w+1)
        ){
            // std::cout << " 4 if " << std::endl;
            return true;
        }
        // std::cout << board[i][j] << std::endl;
        board[i][j] = false;    // 若当前坐标四周都没有找到可行区域，则让本子中记录格子恢复记录为未走过；
                                // 因为可能其他坐标点关联的四周可作为可行区域,可手调例子 [[A,B,C],[B,E,D],[F,G,G]],"ABCDEBF" 体会
        return false;
    }
};