题目链接:http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1259

题解分析:广搜爆搜就可以了,但要注意:那些非0和1的数字,相同的地方一定要提前存起来、、、

代码如下:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
using namespace std;
#define MAX 105

char map[MAX][MAX];
struct nodes{
int a[5000];
int b[5000];
int k;
}d[10];   //储存2-9相同数字的横纵坐标
int n;
int s_x,s_y;   //起始点
int e_x,e_y;   //终止点

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

void DFS(){
int i,j;
int x,y,cnt;
int xx,yy,t;
bool v[MAX][MAX];
queue<int>Q;
Q.push(s_x);
Q.push(s_y);
Q.push(0);
memset( v,0,sizeof(v) );
v[s_x][s_y] = 1;
while( !Q.empty() ){
x = Q.front();  Q.pop();
y = Q.front();  Q.pop();
cnt = Q.front(); Q.pop();
if( x==e_x && y==e_y ){
printf( “%d\n”,cnt );
return ;
}
for( i=0; i<4; i++ ){
xx = x+dir[i][0];
yy = y+dir[i][1];
if( ( xx>=1 && xx<=n ) && ( yy>=1 && yy<=n ) )
;
else
continue;
if( map[xx][yy] == ‘1’ )
continue;
else if( map[xx][yy]>=’2′ && map[xx][yy]<=’9′ && !v[xx][yy] ){     //相同数字入一次队列即可
t = map[xx][yy] – ‘0’;
for( j=0; j<d[t].k; j++ ){
Q.push( d[t].a[j] );
Q.push( d[t].b[j] );
Q.push( cnt+1 );
v[ d[t].a[j] ][ d[t].b[j] ] = 1;
}
}
else if( !v[xx][yy] ){
Q.push( xx );
Q.push( yy );
Q.push( cnt+1 );
v[xx][yy] = 1;
}
}
}
printf( “Oh No!\n” );
return ;
}

int main(){
int i,j,t;
while( scanf( “%d”, &n ) != EOF ){
getchar();
for( i=0; i<10; i++ )
d[i].k = 0;
for( i=1; i<=n; 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] == ‘E’ ){
e_x = i;
e_y = j;
}
if( map[i][j]>’1′ && map[i][j]<=’9′ ){       //存储2-9相同数字的横纵坐标
t = map[i][j]-‘0’;
d[t].a[ d[t].k ] = i;
d[t].b[ d[t].k ] = j;
d[t].k ++;
}
}
getchar();
}
DFS();
}
return 0;
}

 

发表评论

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

Post Navigation