leetcode79 单词搜索

题目

单词搜索

分析

解法：dfs
没啥可讲的，dfs初级练习题目（当然bfs也没问题）。

代码

class Solution {
private:
    bool find;
    int row;
    int col;
    
    void dfs(int cur_i, int cur_j, int k, string& str, vector<vector<char>>& board) {
        //已经找到
        if (find) {
            return;
        }
        //匹配完成，标记成已找到
        if (k >= str.size()) {
            find = true;
            return;
        }
        //边界判断，重复访问过滤，值判断
        if (cur_i < 0 || cur_i >= row || cur_j < 0 || cur_j >= col || 
            board[cur_i][cur_j] == '1' ||board[cur_i][cur_j] != str[k]) {
            return;
        }

        char ch = board[cur_i][cur_j];
        board[cur_i][cur_j] = '1';

        dfs(cur_i + 1, cur_j, k + 1, str, board);
        dfs(cur_i - 1, cur_j, k + 1, str, board);
        dfs(cur_i, cur_j + 1, k + 1, str, board);
        dfs(cur_i, cur_j - 1, k + 1, str, board);

        board[cur_i][cur_j] = ch;
    }
public:
    bool exist(vector<vector<char>>& board, string word) {
        find = false;
        row = board.size();
        col = board[0].size();

        for (int i = 0; !find && i < row; i++) {
            for (int j = 0; !find && j < col; j++) {
                dfs(i, j, 0, word, board);
            }
        }

        return find;
    }
};