首页 » 编程之美 » 正文

[leetcode_79]Word Search

简单搜索题。

class Solution {
public:
    bool result;
    bool exist(vector<vector<char> > &board, string word) {
        vector<vector<int>>flag;
        flag.clear();
        for(int i = 0;i < board.size();i++) {
            vector<int>item(board[i].size(),0);
            flag.push_back(item);
        }
        result = false;
        int pos = 0;
        for(int i = 0;i < board.size();i++) {
            for(int j = 0;j < board[i].size();j++) {
                if(flag[i][j] == 0 && board[i][j] == word[pos]) {
                    flag[i][j] = 1;
                    pos++;
                    existStep(board,flag,word,i,j,pos);
                    pos--;
                    flag[i][j] = 0;<br />
                }
            }
        }
        return result;
    }
private:
    void existStep(vector&amp;lt;vector&amp;lt;char&amp;gt;&amp;gt;&amp;amp;board,vector&amp;lt;vector&amp;lt;int&amp;gt;&amp;gt;&amp;amp;flag,string word,int x,int y,int pos) {
        if(result)return;
        if(pos &amp;gt;= word.length()) {
            result = true;
            return;
        }
        int walk[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
        for(int i = 0;i &amp;lt; 4;i++) {
            int xn = x + walk[i][0];
            int yn = y + walk[i][1];
            if(xn &amp;lt; 0 || xn &amp;gt;=board.size() || yn &amp;lt; 0 || yn &amp;gt;= board[0].size())continue;
            if(flag[xn][yn] == 1 || board[xn][yn] != word[pos])continue;
            flag[xn][yn] = 1;
            pos++;
            existStep(board,flag,word,xn,yn,pos);
            pos--;
            flag[xn][yn] = 0;
        }
    }
};

发表评论