【Leetcode】79. Word Search（DFS）

客官°小女子只卖身不卖艺 2022-04-23 15:56 136阅读 0赞

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

**Example:**

board =
    [
      ['A','B','C','E'],
      ['S','F','C','S'],
      ['A','D','E','E']
    ]
    
    Given word = "ABCCED", return true.
    Given word = "SEE", return true.
    Given word = "ABCB", return false.

题目大意：

给出一个二维的数组，找出其中相邻元素（上下左右）是否能组成给出的一个Word，是的话返回true。

解题思路：

直接dfs，只faster than 5%。以后少写暴力搜索，当年写个搜索还行，现在懂行的人多了。搜索都变暴力。。。。:=(

class Solution {
    private:
        bool ans;
        int xx[4] = {0,0,-1,1};
        int yy[4] = {-1,1,0,0};
        int n,m;
        int tmp;
        vector<vector<bool> > map_is; 
        void dfs(int x, int y,vector<vector<char> > board, string word){
            // cout<< x << " " << y << endl;
            // cout<< word.length() << endl;
            if(tmp==word.length()){
                ans = true;
                return;
            }
            for(int i=0;i<4;i++){
                int cor_x = x+xx[i];
                int cor_y = y+yy[i];
                if(vaild(cor_x,cor_y,board,word)){
                    tmp++;
                    map_is[cor_x][cor_y] = true;
                    dfs(cor_x,cor_y,board,word);
                    map_is[cor_x][cor_y] = false;
                    if(ans == true) return;
                    tmp--;
                }
            }
        }
        bool vaild(int x,int y,vector<vector<char> > board, string w){
            if(x < n&&x>=0&&y<m&&y>=0 ){
                if(board[x][y]==w[tmp]&&map_is[x][y]==false){
                    return true;
                }
            }
            return false;
        }
    public:
        bool exist(vector<vector<char>>& board, string word) {
            ans = false;
            n = board.size();
            m = board[0].size();
            for(int i = 0;i<n;i++){
                vector<bool> tmp_map;
                for(int j = 0;j<m;j++){
                    tmp_map.push_back(false);
                }
                map_is.push_back(tmp_map);
            }
            
            for(int i = 0;i<n;i++){
                for(int j = 0;j<m;j++){
                    if(board[i][j]==word[0]){
                        tmp=1;
                        map_is[i][j] = true;
                        dfs(i,j,board, word);
                        map_is[i][j] = false;
                        if(ans == true) return ans;
                    }
                }
            }
    
            
            return false;
        }
    };