付翔的专栏
在鄙视中成长 记录成长的点滴
posts - 106,  comments - 32,  trackbacks - 0

#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*-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 付翔 阅读(223) 评论(0)  编辑 收藏 引用 所属分类: ACM 数据结构

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理



<2010年10月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

留言簿(2)

随笔分类

随笔档案

文章分类

文章档案

CSDN - 我的blog地址

博客

搜索

  •  

最新评论

阅读排行榜

评论排行榜