天天看點

hdu1010

#include <stdio.h>

#include <string.h>

#include <math.h>

int n,m,t;

char map[10][10];

int flag;

int di,dj,wall;

int to[4][2] = {{0,-1},{0,1},{-1,0},{1,0}};

void dfs(int si,int sj,int cnt)//深搜

{

int i,tem;

if(si>n || sj>m || si<=0 || sj <= 0)//出界

return ;

if(cnt == t && si == di && sj == dj)//到達終點

flag = 1;

if(flag)

return ;

int s1 = si-di;

int s2 = sj-dj;

if(s1<0)

s1=-s1;

if(s2<0)

s2=-s2;

tem = t-cnt - s1 - s2;

if(tem<0 || tem&1)//看剩下的時間能能否到達終點,tem&1則是判斷其是否偶數,根據LCY的奇偶性剪枝可得tem必須是偶數,是奇數則不行

return;

for(i = 0; i<4; i++)

{

if(map[si+to[i][0]][sj+to[i][1]]!='X')

{

map[si+to[i][0]][sj+to[i][1]]='X';//走過的地方變為牆

dfs(si+to[i][0],sj+to[i][1],cnt+1);

map[si+to[i][0]][sj+to[i][1]]='.';//迷宮還原,以便下次廣搜

}

}

return ;

}

int main()

{

int i,j,si,sj;

while(~scanf("%d%d%d%*c",&n,&m,&t))

{

if(!n && !m && !t)

break;

wall = 0;

for(i = 1; i<=n; i++)

{

for(j = 1; j<=m; j++)

{

scanf("%c",&map[i][j]);

if(map[i][j] == 'S')

{

si = i;

sj = j;

}

else if(map[i][j] == 'D')

{

di = i;

dj = j;

}

else if(map[i][j] == 'X')

wall++;

}

getchar();

}

if(n*m-wall<=t)//t是代表要走的步數,步數加牆數必須小于總格子數的,因為所有格子中還包括了S和D,這是剪枝

{

printf("NO\n");

continue;

}

flag = 0;

map[si][sj] = 'X';//出發點是不可能再走的了,變為牆

dfs(si,sj,0);

if(flag)

printf("YES\n");

else

printf("NO\n");

}

return 0;

}