剑指12：矩阵中的路径

传送门

nowcoder
leetcode

题目描述

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。
如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。

C++ 代码 - nowcoder

/*
    DFS：回溯法 
*/ 
class Solution {
public:
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        if (str == nullptr || rows <= 0 || cols <= 0) return false;

        vector<vector<char>> board(rows, vector<char>(cols));
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                board[i][j] = matrix[i * cols + j];
            }
        }
        
        vector<vector<bool>> visited(rows, vector<bool>(cols, false));
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (hasPathCore(board, str, visited, i, j, 0))
                    return true;
            }
        }
        return false;
    }

    bool hasPathCore(vector<vector<char>> &board, char* str, vector<vector<bool>> &visited, 
                int x, int y, int index) {
        if (index == strlen(str)) return true;
        if (x < 0 || y < 0 || x >= board.size() || y >= board[0].size()) return false;
        if (visited[x][y]) return false; // 之前访问过，剪枝
        if (board[x][y] != str[index]) return false; // 不相等，剪枝

        visited[x][y] = true;
        int dx[] = { -1, 0, 1, 0}, dy[] = { 0, 1, 0, -1};
        for (int i = 0; i < 4; i++) {
            if (hasPathCore(board, str, visited, x + dx[i], y + dy[i], index + 1))
                return true;
        }
        visited[x][y] = false; // 回溯，便于下一次遍历搜索
        return false;
    }
};

C++ 代码 - leetcode

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int rows = board.size(), cols = board[0].size();
        if (word.empty() || rows <= 0 || cols <= 0) return false;

        vector<vector<bool>> visited(rows, vector<bool>(cols, false));
        for (int i = 0; i < rows; i ++) {
            for (int j = 0; j < cols; j ++) {
                if (dfs(board, word, visited, i, j, 0)) return true;
            }
        }
        return false;
    }

    bool dfs(vector<vector<char>>& board, string word, vector<vector<bool>>& visited,
        int x, int y, int index) {
        if (index == word.size()) return true;
        if (x < 0 || y < 0 || x >= board.size() || y >= board[0].size()) return false;
        if (visited[x][y]) return false; // 之前访问过，剪枝
        if (board[x][y] != word[index]) return false; // 不相等，剪枝

        visited[x][y] = true;
        int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };
        for (int i = 0; i < 4; i ++) {
            if (dfs(board, word, visited, x + dx[i], y + dy[i], index + 1)) return true;
        }
        visited[x][y] = false; // 回溯，便于下一次遍历搜索
        return false;
    }
};