79. 单词搜索——搜索与回溯

class Solution {
public:
    bool flag = false;
    bool exist(vector>& board, string word) {
        int rows = board.size(), columns = board[0].size();
        if(rows * columns < word.length())
            return false;
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < columns; j++){
                if(board[i][j] == word[0]){
                    board[i][j] = '1';  //遍历过的置1
                    backtrack(board, word, i, j, 1);
                    board[i][j] = word[0];
                }
                if(flag)
                    return true;
            }
        }
        return flag;
    }
    void backtrack(vector>& board, string& word, int row, int column, int level){
        if(level == word.length()){
            flag = true;
            return;
        }
        if(flag)
            return;
        if(row >= 1 && board[row - 1][column] != '1' && board[row - 1][column] == word[level]){ //向上搜索
            board[row - 1][column] = '1';
            backtrack(board, word, row - 1, column, level + 1);
            board[row - 1][column] = word[level];
            if(flag)
                return;
        }
        if(row + 1 <= board.size() - 1 && board[row + 1][column] != '1' && board[row + 1][column] == word[level]){  //向下搜索，不能写成row <= board.size() - 2
            board[row + 1][column] = '1';                                                                           //因为size()是无整形变量，不能为负数
            backtrack(board, word, row + 1, column, level + 1);                                                     //board.size() - 2 < 0 存在，会导致结果出错
            board[row + 1][column] = word[level];
            if(flag)
                return;
        }
        if(column >= 1 && board[row][column - 1] != '1' && board[row][column - 1] == word[level]){  //向左搜索
            board[row][column - 1] = '1';
            backtrack(board, word, row, column - 1, level + 1);
            board[row][column - 1] = word[level];
            if(flag)
                return;
        }
        if(column + 1 <= board[0].size() - 1 && board[row][column + 1] != '1' && board[row][column + 1] == word[level]){    //向右搜索
            board[row][column + 1] = '1';
            backtrack(board, word, row, column + 1, level + 1);
            board[row][column + 1] = word[level];
            if(flag)
                return;
        }
    }
};

Accepted
82/82 cases passed (184 ms)
Your runtime beats 89.91 % of cpp submissions
Your memory usage beats 42.13 % of cpp submissions (7.8 MB)