独轮车 - 数据结构与算法

得分:0

#include<stdio.h>
struct colornode
{
int row; //该状态的行
int col; // 列
int color; // 颜色
int num; // 最小步数
};
int search(); //广搜返回目标结点的最小步数
void readdata(); //读入数据
void init(); //初始化
struct colornode moveahead(struct colornode u,int direction); //返回u向前走一格得到的结点
int used(struct colornode v); //判断该结点是否是到达过的结点
void addtoopen(struct colornode v); //加入到open表
int islegal(struct colornode v); //如果该结点是合法的结点(未越界且是空格)
int isaim(struct colornode v); //判断该结点是否是目标结点
struct colornode takeoutofopen(); //从open表中取出一个结点并把该结点从open表中删除
struct colornode s,t; //s:起始结点；t目标结点
struct colornode open[200]; //open表
int head,tail,openlen=200; //open表相关数据
int direct[4][2]={{0,-1},{1,0},{0,1},{-1,0}};//向左、下、右、上四个方向转时，行列的增加值
int a[20][20],n=20; //a数组表示迷宫；n为迷宫边长
int b[20][20][5]; //b数组表示搜索时的所有状态(0：未访问；1：已访问)
void main()
{
int number[15]={0};
int time,k,i=0;
scanf("%d",&time);
k=time;
while(time)
{
readdata(); //读取数据
init(); //初始化
number[i]=search(); //广搜并返回最小步数
time--;
i++;
}
for(i=0;i<k;i++)
{
printf("%d\n",number[i]); //打印结果
}
}
int search() //广搜返回目标结点的最小步数
{
struct colornode u,v;
int i;
init();
while(head!=tail)
{
u=takeoutofopen();
for(i=0;i<4;i++)
{
v=moveahead(u,i);//u向前走一格得到新结点v
if(islegal(v)) //如果该结点是合法的结点(未越界且是空格)
{
if(isaim(v)) //判是否是目标结点
return(v.num);
if(!used(v)) //如果是未到达过的结点
addtoopen(v); //加入到open表
}
}

}
}
int used(struct colornode v) //判断该结点是否是到达过的结点
{
if(b[v.row][v.col][v.color]==0)
return(0);
else
return(1);
}
void addtoopen(struct colornode v) //加入到open表
{
open[tail++]=v;
tail=tail%openlen;
b[v.row][v.col][v.color]=1;
}
struct colornode takeoutofopen() //从open表中取出一个结点并把该结点从open表中删除
{
struct colornode v;
v=open[head++];
head=head%openlen;
return(v);
}
void init() //初始化
{
int i,j,k;
for(i=0;i<n;i++) //所有状态初始化
for(j=0;j<n;j++)
for(k=0;k<5;k++)
b[i][j][k]=0;
head=0;
tail=0;
addtoopen(s); //把起始点加入到open表
}
void readdata() //读入数据
{
char str[50];
int i,j;
s.color=0;
scanf("%d%d",&s.row,&s.col); //读入起始结点信息
scanf("%d%d%d",&t.row,&t.col,&t.color); //读入目标结点信息
getchar();
for(i=0;i<n;i++)
{
gets(str);
for(j=0;j<n;j++)
{
if(str[j]=='.') //读入数据'.'表示空格
a[i][j]=0; //存储时 0：表示空格
else
a[i][j]=1; // 1：表示墙
}
}
}
int isaim(struct colornode v) //判断该结点是否是目标结点
{
if(v.row==t.row&&v.col==t.col&&v.color==t.color)
return 1;
else
return 0;
}
int islegal(struct colornode v) //如果该结点是合法的结点(未越界且是空格)
{
if(v.row<0||v.row>=n||v.col<0||v.col>=n) //若越界
return 0;
if(a[v.row][v.col]==0) //0：表示空格
return 1;
return 0;
}
struct colornode moveahead(struct colornode u,int direction) //返回u向前走一格得到的结点
{
struct colornode v;
switch(direction)
{
case 0: u.col--; //左
break;
case 1: u.row++; //下
break;
case 2: u.col++; //右
break;
case 3: u.row--; //上
}
v.row=u.row;
v.col=u.col;
v.color=(u.color+1)%5;
v.num=u.num+1;
return(v);
}