ZOJ2110-Tempter of the Bone(HDU1010)
题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2110
题意描述:给一幅地图,按要求从一个点到另一个点,且时间恰好等于给出的时间、、
题意分析:深搜吧、、、啊,纠结,输出的NO不小心写成No了,没发现,调了好久,还拿以前写的程序对照,然后改了很久、、、啊…………
详细代码解释:http://user.qzone.qq.com/1156638549/infocenter#!app=2&via=QZ.HashRefresh&pos=1315823894

代码如下:

#include<stdio.h>
#include<string.h>
#include<math.h>

char map[10][10];
int v[10][10];
int m,n,time;
int s_x,s_y,e_x,e_y;
int flag;

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

void DFS( int s, int e, int tept ){
int i;
if( s==e_x && e==e_y && tept==time ){
flag = 1;
return ;
}
int check = ( ( time-tept ) – fabs( e_x-s )-fabs( e_y-e ) );
if( check<0 || check%2 ){
return ;
}
for( i=0; i<4; i++ ){
int xx = s + dir[i][0];
int yy = e + dir[i][1];
if( xx<1 || xx>m || yy<1 || yy>n )
continue;
if( map[xx][yy]!=’X’ && !v[xx][yy] ){
v[xx][yy] = 1;
DFS( xx, yy, tept+1 );
if( flag == 1 )
return ;
v[xx][yy] = 0;
}
}
return ;
}

int main(){
int i,j;
int wall;
while( scanf( “%d%d%d”, &m, &n, &time ) && ( m+n+time ) ){
getchar();
wall = 0;
for( i=1; i<=m; i++ ){
for( j=1; j<=n; j++ ){
scanf( “%c”, &map[i][j] );
if( map[i][j] == ‘S’ ){
s_x = i;  s_y = j;
}
if( map[i][j] == ‘D’ ){
e_x = i;  e_y = j;
}
if( map[i][j] == ‘X’ )
wall ++;
}
getchar();
}
if( m * n – wall < time ){
printf( “NO\n” );
continue;
}
flag = 0;
memset( v, 0, sizeof( v ) );
v[s_x][s_y] = 1;
DFS( s_x, s_y, 0 );
if( flag == 1 )
printf( “YES\n” );
else
printf( “NO\n” );
}
return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation