leetcode || 79、Word Search
來源：程序員人生 發布時間：2015-04-30 09:06:59 閱讀次數：3764次
problem：
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,
Given board =
[
["ABCE"],
["SFCS"],
["ADEE"]
]
word =
"ABCCED", -> returns
true,
word =
"SEE", -> returns
true,
word =
"ABCB", -> returns
false.
Hide Tags
Array Backtracking
題意：在1個字符矩陣中搜索1個字，每一個字符只能使用1次，搜索方向為上下左右
thinking：
（1）肯定方法：全局搜索滿足條件的解，使用DFS
（2）深搜成功的條件是：深搜成功1次，步數+1，直到深搜的步數到達word的長度
（3）新開1個矩陣大小的2維數組，記錄矩陣的字符是不是用過，先在矩陣中搜索word[0]的位置，1次為出發點開始深搜，每次搜索上下左右4個方向
code：
class Solution {
private:
bool flag;
public:
bool exist(vector<vector<char> > &board, string word) {
int m=board.size();
int n=board[0].size();
int Maxdep=word.size();
flag = false;
vector<int> a1(n,0);
vector<vector<int> > array(m,a1);
for(int i=0;i<m;i++) //尋覓搜索出發點
{
for(int j=0;j<n;j++)
{
if(flag) //加快搜索
return true;
if(board[i][j]==word[0])
dfs(0,Maxdep,i,j,array,board,word);
}
}
return flag;
}
protected:
void dfs(int dep,int Maxdep,int x, int y,vector<vector<int> > &array,
vector<vector<char> > &board, string word)
{
if(flag) //不能去掉，去掉就超時了
return;
int m=board.size();
int n=board[0].size();
if(dep==Maxdep) //這個必須放在x,y 邊界判斷的前面
{
flag=true;
return ;
}
if(x<0 || x>=m || y<0 || y>=n)
return;
if(array[x][y]==1)
return;
if(board[x][y]==word[dep]) //4個方向深搜
{
array[x][y]=1;
dfs(dep+1,Maxdep,x⑴,y,array,board,word);
dfs(dep+1,Maxdep,x,y⑴,array,board,word);
dfs(dep+1,Maxdep,x+1,y,array,board,word);
dfs(dep+1,Maxdep,x,y+1,array,board,word);
array[x][y]=0;
}
}
};
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
