Skip to content

Instantly share code, notes, and snippets.

@osjayaprakash
Created December 22, 2012 18:41
Show Gist options
  • Save osjayaprakash/4360421 to your computer and use it in GitHub Desktop.
Save osjayaprakash/4360421 to your computer and use it in GitHub Desktop.
SPOJ, DFS
#include <iostream>
#include <cstring>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
char str[]="ALLIZZWELL";
int v[105][105];
int n,m;
vector<string> inp;
int fn(int r, int c, int l)
{
//cout << r << ' ' << c << ' ' << l << endl;
if(l==10)
return true;
v[r][c]=1;
for(int i=-1;i<=1;i++)
for(int j=-1;j<=1;j++)
{
int r1=r+i, c1=c+j;
if((i==0&&j==0)||r1<0||r1>=n||c1<0||c1>=m||inp[r1][c1]!=str[l])
continue;
if(v[r1][c1])
continue;
if( fn(r1,c1,l+1) ){
v[r][c]=0;
return true;
}
}
v[r][c]=0;
return false;
}
int main()
{
int tc;
cin >> tc;
while(tc--){
inp.clear();
cin>>n>>m;
for(int i=0;i<n;i++ ){
string a;
cin>>a;
inp.push_back(a);
}
bool f=false;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(inp[i][j]=='A' && fn(i,j,1)){
f=true; break;
}
if(f)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment