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 =
[ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ]
word =
"ABCCED", -> returns
true,
word =
"SEE", -> returns
true,
word =
"ABCB", -> returns
false.
訪問過的元素不能再訪問,發(fā)現(xiàn)大家的實現(xiàn)都是用個附加結(jié)構(gòu)標(biāo)記訪問過的.就地賦值個'\0'后面再恢復(fù)好啦.......
bool exist(vector<vector<char>>& board,int i,int j,string::iterator beg,string::iterator end)
{
bool res=true;
char cur=*beg++;
if(board[i][j]!=cur)return false;
if(beg==end)return true;
board[i][j]=0;
do{//上下左右
if(i+1<board.size()&&exist(board,i+1,j,beg,end))
break;
if(i-1>=0&&exist(board,i-1,j,beg,end))
break;
if(j+1<board[0].size()&&exist(board,i,j+1,beg,end))
break;
if(j-1>=0&& exist(board,i,j-1,beg,end))
break;
res=false;
}while(0);
board[i][j]=cur;
return res;
}
bool exist(vector<vector<char>>& board, string word) {
char beg=word[0];
for(int i=0;i<board.size();++i)
for(int j=0;j<board[0].size();++j)
if(exist(board,i,j,word.begin(),word.end()))
return true;
return false;
}