# Simple DFS Solution without explanation in C++(6ms)

• class Solution {
public:
int n,m;
int cnt[333];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
bool isok(int cx,int cy)
{
return cx >= 0 && cx < n && cy >= 0 && cy < m;
}
bool dfs(int cx,int cy,int dp,int len,vector<vector<char> >& board,string& word,vector<vector<bool> >&flag)
{

``````    if(board[cx][cy] != word[dp])
return false;
if(dp == len - 1)
return true;
for(int i = 0;i < 4;++ i)
{
int tx = cx + dx[i];
int ty = cy + dy[i];
if(isok(tx,ty) && !flag[tx][ty]){
flag[tx][ty] = true;
if(dfs(tx,ty,dp + 1,len,board,word,flag))
return true;
flag[tx][ty] = false;
}
}
return false;
}
bool exist(vector<vector<char>>& board, string word) {
n = board.size();
if(!n)
return false;
m = board[0].size();
memset(cnt,0,sizeof(cnt));
for(int i = 0;i < n;++ i)
for(int j = 0;j < m;++ j)
cnt[board[i][j]] ++;
int len = word.size();
if(!len)
return false;
for(int i = 0;i < len;++ i){
cnt[word[i]] --;
if(cnt[word[i]] < 0)
return false;
}
vector<vector<bool> >flag(n,vector<bool>(m,false));
for(int i = 0;i < n;++ i){
for(int j = 0;j < m;++ j){
flag[i][j] = true;
if(dfs(i,j,0,len,board,word,flag))
return true;
flag[i][j] = false;
}
}
return false;
}
``````

};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.