class Solution {
public:
vector<char> v[6];
string target;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
bool visited[6][6];
int m,n;
bool find(int x,int y,int cur){
bool ret = false;
if(cur == target.length() -1){
return true;
}
for(int i=0;i<4;i++){
int nx = x+dx[i];
int ny = y+dy[i];
if(nx<0||nx>=n||ny<0||ny>=m){
continue;
}
if(visited[ny][nx]){
continue;
}
if(target[cur+1] == v[ny][nx]){
visited[ny][nx]=true;
ret = max(ret,find(nx,ny,cur+1));
visited[ny][nx]=false;
}
}
return ret;
}
bool exist(vector<vector<char>>& board, string word) {
target=word;m=board.size();n=board[0].size();
for(int i=0;i<m;i++){
for(char a: board[i]){
v[i].push_back(a);
}
}
bool ans = false;
for(int i=0;i<m;i++){
for(int t=0;t<n;t++){
memset(visited,false,sizeof(visited));
if(v[i][t]==target[0]){
visited[i][t]=true;
if(find(t,i,0)){
return true;
}
}
}
}
return ans;
}
};