剑指 Offer 12. 矩阵中的路径

题目描述

LeetCode:https://leetcode.cn/problems/ju-zhen-zhong-de-lu-jing-lcof/

只要是不越界，没访问过，且字符匹配，我们都先把这个格子标记为可访问，然后从这个格子出发，如果发现周围的格子要么越界、要么字符不匹配、要么已经访问过，我们重新把该格子设置为未访问

把该格子设置为未访问，是因为从当前格子不能走过去，但是可能从其他的格子能走过去，所以要恢复格子未访问的状态，下次才能继续访问

class Solution {
public:
    // 从board[i][j]开始查找word[k]
    bool dfs(vector>& board, int i, int j, vector>& visited, string word, int k) {
        if (board[i][j] != word[k]) {
            // 字符不匹配
            return false;
        }

        if (k == word.size() - 1) {
            // 当前字符匹配，且已经匹配到最后一个字符
            return true;
        }

        // 字符匹配则标记为表示访问过
        visited[i][j] = true;

        const pair dirs[4] = { {0, 1} , {1, 0}, {-1, 0}, {0, -1} };
        for (pair dir : dirs) {
            int x = i + dir.first;
            int y = j + dir.second;
			// 检查新方向(x, y)的合法性，执行dfs后就不用再检查了
            if (x >= 0 && x < board.size() && y >= 0 && y < board[0].size() && !visited[x][y]) {
                // 检查越界 && 没有访问过，则往这个点继续访问，实现dfs
                if (dfs(board, x, y, visited, word, k + 1)) {
                    return true;
                }
            }
        }
        
        visited[i][j] = false;
        return false;
    }

    bool exist(vector>& board, string word) {
        int m = board.size();
        int n = board[0].size();
        vector> visited(m, vector(n, false));

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(dfs(board, i, j, visited, word, 0)){
                    return true;
                }
            }
        }
        return false;
    }
};

bool dfs(vector>& board, int i, int j, vector>& visited, string word, int k)

函数dfs的功能：board[i][j]出发，在board中寻找word从第k个字符开始的字符串，visited为true则不能访问，找到则返回true，没找到则返回false

• 字符不匹配直接返回false
• 字符串匹配完成则返回true
• 往4个方向继续匹配字符