Is there any trick in test #10
Posted by
akademi 12 Mar 2005 15:14
I know I can calculate the anwser directly,but I used DFS algorithm at first.I think it can solve this problem too,but I got WA on test #10,who can tell me WHY? thx.
My code:
/* ural1164 */
#include<iostream>
#include<string.h>
using namespace std;
const way[4][2]={{1,0},{0,-1},{-1,0},{0,1}};
int m,n,p;
char map[15][15];
bool check[15][15];
bool flag,fflag;
char word[150][300];
void init()
{
int i,j;
cin>>n>>m>>p;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++) cin>>map[i][j];
for(i=1;i<=p;i++) cin>>word[i];
fflag=false;
}
void find(int x,int y,int d,int l)
{
int i,xx,yy;
if(flag) return;
check[x][y]=true;
if(l==strlen(word[d])+1)
{
flag=true;
return;
}
for(i=0;i<=3;i++)
{
xx=x+way[i][0];
yy=y+way[i][1];
if(map[xx][yy]==word[d][l-1] && !check[xx][yy])
find(xx,yy,d,l+1);
}
if(flag) return;
check[x][y]=false;
return;
}
void out()
{
int i,j,l;
char w;
char ans[300],*p;
p=ans;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(!check[i][j])
*(p++)=map[i][j];
*p='\0';
l=strlen(ans);
for(i=l-1;i>=0;i--)
for(j=0;j<=i-1;j++)
if(ans[j]>ans[j+1])
{
w=ans[j];
ans[j]=ans[j+1];
ans[j+1]=w;
}
cout<<ans<<endl;
}
void search(int x)
{
bool check1[15][15];
int i,j;
if(x==p+1)
{
out();
fflag=true;
}
if(fflag) return;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(map[i][j]==word[x][0] && !check[i][j])
{
memmove(check1,check,sizeof(check));
flag=false;
find(i,j,x,2);
if(flag) search(x+1);
memmove(check,check1,sizeof(check1));
}
}
void work()
{
memset(check,false,sizeof(check));
search(1);
}
int main()
{
init();
work();
return 0;
}