题目链接:http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=388#problem/H

做了很长时间才出来,表示弱爆了;题意是求最短时间,用bfs,每次状态入队列就ok了;

my code:

#include <stdio.h>
#include <string.h>
#define MAX 26
int visit[MAX][MAX][4][5];//4:0北,1东,2南,3西 |5:0green,1black,2red,3blue,4white
int plusx[4]={-1,0,1,0},plusy[4]={0,1,0,-1};//根据上一次的方向来判断下一次移动位置的坐标(开始没想到,搞的好复杂),简化了很多代码
int ax,ay;//存起始点和终点的地址
char map[MAX][MAX];//存图
int m,n;
struct s
{
int time;//累计用时
int desx,desy;//存地址
int color;//0green,1black,2red,3blue,4white
int pot;////4:0北,1东,2南,3西
}que[200000];//队列
int pre,bottom;//队列指针
int bfs()//一般的广搜
{
int x,y,color,pot,time,x_next,y_next,pot_next;

que[pre].desx=ax;//起始点入队
que[pre].desy=ay;
que[pre].color=0;
que[pre].pot=0;
que[pre++].time=0;

while(bottom<pre)
{
x=que[bottom].desx;//为了简化代码书写
y=que[bottom].desy;
color=que[bottom].color;
pot=que[bottom].pot;
time=que[bottom++].time;

x_next=x+plusx[pot];
y_next=y+plusy[pot];
if(map[x_next][y_next]==’T’&&(color+1)%5==0)
return time+1;
if(( x_next>=0&&x_next<m)&&(y_next>=0&&y_next<n)&&visit[x_next][y_next][pot][(color+1)%5]!=1&&map[x_next][y_next]!=’#’)//前进
{
que[pre].desx=x_next;
que[pre].desy=y_next;
que[pre].color=(color+1)%5;
que[pre].pot=pot;
que[pre++].time=time+1;
visit[x_next][y_next][pot][(color+1)%5]=1;
}

pot_next=(pot+1)%4;
if(visit[x][y][pot_next][color]!=1)//右转
{
que[pre].desx=x;
que[pre].desy=y;
que[pre].color=color;
que[pre].pot=pot_next;
que[pre++].time=time+1;
visit[x][y][pot_next][color]=1;
}

pot_next=(pot+3)%4;
if(visit[x][y][pot_next][color]!=1)//左转
{
que[pre].desx=x;
que[pre].desy=y;
que[pre].color=color;
que[pre].pot=pot_next;
que[pre++].time=time+1;
visit[x][y][pot_next][color]=1;
}
}
return -1;
}
int main()
{
int mini_time,i,j,flag,t=0;
while(scanf(“%d%d”,&m,&n),m||n)
{
t++;
getchar();
pre=bottom=0;//队列指针
flag=0;
memset(visit,0,sizeof(visit));
memset(map,0,sizeof(map));
for(i=0;i<m;i++)//数据的录入
gets(map[i]);

for(i=0;i<m;i++)//查找起始点信息
{
for(j=0;j<n;j++)
if(map[i][j]==’S’)
{
ax=i;
ay=j;
visit[i][j][0][0]=1;
flag=1;
break;
}
if(flag)
break;
}
mini_time=bfs();//bfs返回-1则说明没有符合条件路径,否则返回最小时间

if(t!=1)//一下是输出格式控制
printf(“\n”);
printf(“Case #%d\n”,t);
if(mini_time==-1)
printf(“destination not reachable\n”);
else
printf(“minimum time = %d sec\n”,mini_time);
}
return 0;
}

发表评论

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

Post Navigation