LeetCode 79. 单词搜索

LeetCode 79. 单词搜索
思路：
遍历矩阵，如果能找到一个方案，就返回true。

代码：

class Solution {
public:

    bool exist(vector<vector<char>>& board, string word) {
        //深搜
        for(int i=0;i<board.size();i++)
            for(int j=0;j<board[0].size();j++){
                // x 0 y 0 u 0
                if(dfs(board,word,i,j,0)) return true;
            }
        return false;
    }

    int dx[4]={0,-1,0,1};
    int dy[4]={1,0,-1,0};

    bool dfs(vector<vector<char>> & board,string word,int x,int y,int u){
        if(board[x][y] != word[u]) return false;
        if(u == word.size()-1) return true;

        char t=board[x][y];
        board[x][y]='.';//标记被搜索过了
        for(int i=0;i<4;i++){
            int a=x+dx[i],b=y+dy[i];
            if(a<0 || a>=board.size() || b<0 || b>=board[0].size() || board[a][b] == '.') continue;
            if(dfs(board,word,a,b,u+1)) return true;
        }
        //回溯
        board[x][y]=t;
        return false;
    }
};