题解 | #实习广场投递简历分析(一)#

稍微优化了一下第一个代码，用‘1’表示访问过

class Solution {
public:
    bool exist(vector<vector<char> > &board, string word) {
        int m = board.size();
        int n = board[0].size();
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (dfs(board, word, 0, i, j)) return true;
            }
        }
        return false;
    }

    bool dfs(vector<vector<char> > &board, string& word, int pos, int x, int y)
    {
        if (pos == word.size()) return true;
        if (x < 0 || x >= board.size() || y <0 || y >= board[0].size()) return false;
        if (board[x][y] != word[pos]) return false;
        char t = board[x][y];
        board[x][y] = '1';
        bool a = dfs(board, word, pos + 1, x + 1, y) ||
                 dfs(board, word, pos + 1, x - 1, y) ||
                 dfs(board, word, pos + 1, x, y + 1) ||
                 dfs(board, word, pos + 1, x, y - 1);
        board[x][y] = t;
        return a;
    }
};