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,"SEE",
-> returns true,word = "ABCB",
-> returns false.
题目大意是在矩阵中找是否有word的路径，上下左右都可以
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
int M=board.size();
int N=board[0].size();
vector<vector<int>> v(M,vector<int> (N));
for(int i=0;i<M;i++)
for(int j=0;j<N;j++)
{
if(board[i][j]==word[0])
if(dfs(board,word,i,j,0,v))
return true;
}
return false;
}
bool dfs(vector<vector<char>>& board, string word,int x,int y,int index,vector<vector<int>>& v)
{
int M=board.size();
int N=board[0].size();
if(index==word.size()-1)
return true;
v[x][y]=1;
if(x+1<M&&v[x+1][y]==0&&board[x+1][y]==word[index+1]) //right
if(dfs(board,word,x+1,y,index+1,v))
return true;
if(x-1>=0&&v[x-1][y]==0&&board[x-1][y]==word[index+1]) //left
if(dfs(board,word,x-1,y,index+1,v))
return true;
if(y+1<N&&v[x][y+1]==0&&board[x][y+1]==word[index+1]) //up
if(dfs(board,word,x,y+1,index+1,v))
return true;
if(y-1>=0&&v[x][y-1]==0&&board[x][y-1]==word[index+1]) //down
if(dfs(board,word,x,y-1,index+1,v))
return true;
v[x][y]=0; //如果上下左右都走不下去了，那么之前的都归0
return false;
}
};原文：http://blog.csdn.net/u011391629/article/details/52105237