hdu2102 （dfs）搜索水題

hdu2102 （dfs）搜索水題

題意就不多說了 肯見很多人都是用bfsA的 然後我就果斷用dfs做了 和其他深搜都一樣就是注意下裡面的一些剪枝 不然很容易就超時

#include
#include
#include
using namespace std;


char map[5][15][15];
int mark[5][15][15],t,n,m,flash;
int dir[4][2]={0,1,0,-1,1,0,-1,0};
int dfs(int x,int y,int z,int tt)
{
int i,xx,yy,zz;
if(map[x][y][z]=='P')
{
flash=1;
return 0;
}
else if(map[x][y][z]=='#')
{
if(x==0) xx=1;
else xx=0;
yy=y;
zz=z;
if(mark[xx][yy][zz]==0&&map[xx][yy][zz]!='*')
{
mark[xx][yy][zz]=1;
dfs(xx,yy,zz,tt);
mark[xx][yy][zz]=0;
}
}
else
{
for(i=0;i<4;i++)
{
xx=x;
yy=y+dir[i][0];
zz=z+dir[i][1];
if(yy<0||yy>=n||zz<0||zz>=m) continue;
if(tt+1>t) continue;
if(mark[xx][yy][zz]==0&&map[xx][yy][zz]!='*')
{
mark[xx][yy][zz]=1;
dfs(xx,yy,zz,tt+1);
mark[xx][yy][zz]=0;
}
}
}
return 0;
}
int main()
{
int T,i,j;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&t);
for(i=0;i scanf("%s",map[0][i]);
for(i=0;i scanf("%s",map[1][i]);
map[0][0][0]='.';
memset(mark,0,sizeof(mark));
mark[0][0][0]=1;
flash=0;
dfs(0,0,0,0);
if(flash) printf("YES\n");
else printf("NO\n");
}
return 0;
}