#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include<iostream>
const int maxn = 10;
int map[maxn][maxn] ;
int visted[maxn][maxn] ;
int dir[4][2]={{1,0},{-1,0},{0,-1},{0,1}}; //分別表示下、上、左、右四個方向 x 行坐標 y 列坐標
int startx,starty,endx,endy,n,m,wall,T;
bool flag ;
bool isSave(int x,int y) //看走的是否安全
{
if(x>=0 && x < n && y >=0 && y < m)
return true;
return false;
}
void dfs(int x,int y,int cnt)
{
if(cnt > T)
return ;
if(x == endx && y ==endy && cnt ==T)
{
flag = true;
return ;
}
int i,newx,newy;
for(i = 0; i < 4; i ++ )
{
newx = x + dir[i][0],newy = y + dir[i][1];
if(isSave(newx,newy) && map[newx][newy] &&!visted[newx][newy] )
{
visted[newx][newy] = 1;
dfs(newx,newy,cnt+1);
if(flag) return;
visted[newx][newy] = 0;
}
}
}
int main()
{
int i,j;
char ch;
while(scanf("%d%d%d",&n,&m,&T),n||m||T)
{
memset(visted,0,sizeof(visted));
memset(map,0,sizeof(map));
wall = 0;
flag = false;
getchar();
for(i = 0; i < n; i ++)
{
for(j = 0; j < m; j++)
{
scanf("%c",&ch);
if(ch == 'S')
startx = i,starty=j;
else if(ch == 'D' )
endx = i,endy=j ,map[i][j] = 1;//門也是可走點
else if( ch=='X' ) wall++;
else
map[i][j] = 1;
}
getchar();
}
int temp = T - abs(startx-endx) - abs(starty-endy);
if( temp<0 || temp%2==1 ) printf("NO\n");
else if(n*m -wall <= T )
printf("NO\n");
else
{
visted[startx][starty] = 1;
dfs(startx,starty,0);
printf(flag? "YES\n" :"NO\n");
}
}
return 0;
}
posted on 2010-10-23 09:19
付翔 閱讀(280)
評論(0) 編輯 收藏 引用 所屬分類:
ACM 數據結構