[LeetCode]79.Word Search

【题目】

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.

For example,
Givenboard=

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word="ABCCED", -> returnstrue,
word="SEE", -> returnstrue,
word="ABCB", -> returnsfalse.

【分析】

这是一道深度搜索的问题。

用vector<vector<bool> >visited 记录以访问过的letter。

当处于board[i][j]时你可以向四个方向进行尝试访问，必须满足在边界之内，且没有访问过，等于word中的下一个letter

类似于迷宫，递归回溯。需要一个辅助数组记录走过的位置，防止同一个位置被使用多次。

【代码】

/*********************************
*   日期：2015-01-30
*   作者：SJF0115
*   题目: 79.Word Search
*   网址：https://oj.leetcode.com/problems/word-search/
*   结果：AC
*   来源：LeetCode
*   博客：
**********************************/
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    bool exist(vector<vector<char> > &board, string word) {
        // 行数
        row = board.size();
        // 列数
        col = board[0].size();
        // 判断是否已经使用过
        vector<vector<bool> > visited(row, vector<bool>(col, false));
        for(int i = 0;i < row;++i){
            for(int j = 0;j < col;++j){
                // board[i][j] 作为搜索起点
                if(DFS(board,word,0,visited,i,j)){
                    return true;
                }//if
            }//for
        }//for
        return false;
    }
private:
    int row;
    int col;
    // x,y indicates current position
    // index indicates the length of word finded
    bool DFS(vector<vector<char> > &board,string word,int index,vector<vector<bool> >& visited,int x,int y){
        // Find one word in board
        if(index == word.length()){
            return true;
        }//if
        // edges
        if(x < 0 || y < 0 || x >= row || y >= col){
            return false;
        }//if
        // already visited
        if(visited[x][y]){
            return false;
        }//if
        // not equal
        if(board[x][y] != word[index]){
            return false;
        }//if
        visited[x][y] = true;
        // turn left
        if(DFS(board,word,index+1,visited,x,y-1)){
            return true;
        }//if
        // turn right
        if(DFS(board,word,index+1,visited,x,y+1)){
            return true;
        }//if
        // turn up
        if(DFS(board,word,index+1,visited,x-1,y)){
            return true;
        }//if
        // turn down
        if(DFS(board,word,index+1,visited,x+1,y)){
            return true;
        }//if
        visited[x][y] = false;
        return false;
    }
};


int main(){
    Solution solution;
    vector<vector<char> > board = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
    string word = "ABCCFC";
    bool result = solution.exist(board,word);
    // 输出
    cout<<result<<endl;
    return 0;
}

【代码二】

class Solution {
public:
    bool exist(vector<vector<char> > &board, string word) {
        // 行数
        row = board.size();
        // 列数
        col = board[0].size();
        // 判断是否已经使用过
        vector<vector<bool> > visited(row, vector<bool>(col, false));
        for(int i = 0;i < row;++i){
            for(int j = 0;j < col;++j){
                // board[i][j] 作为搜索起点
                if(board[i][j] == word[0]){
                    if(DFS(board,word,0,visited,i,j)){
                        return true;
                    }//if
                }//if
            }//for
        }//for
        return false;
    }
private:
    int row;
    int col;
    // x,y indicates current position
    // index indicates the length of word finded
    bool DFS(vector<vector<char> > &board,string word,int index,vector<vector<bool> >& visited,int x,int y){
        if(board[x][y] != word[index]){
            return false;
        }//if
        visited[x][y] = true;
        // Find one word in board
        if(index+1 == word.length()){
            return true;
        }//if
        // next letter
        // turn left
        if(y - 1 >= 0 && !visited[x][y-1]){
            if(DFS(board,word,index+1,visited,x,y-1)){
                return true;
            }//if
        }//if
        // turn right
        if(y + 1 < col && !visited[x][y+1]){
            if(DFS(board,word,index+1,visited,x,y+1)){
                return true;
            }//if
        }//if
        // turn up
        if(x - 1 >= 0 && !visited[x-1][y]){
            if(DFS(board,word,index+1,visited,x-1,y)){
                return true;
            }//if
        }//if
        // turn down
        if(x + 1 < row && !visited[x+1][y]){
            if(DFS(board,word,index+1,visited,x+1,y)){
                return true;
            }//if
        }//if
        // left right up down all not
        visited[x][y] = false;
        return false;
    }
};