//本程序找出迷宫最短路径，如果路径不止一条，程序将找出所有的最短路径
#include <iostream>
using namespace std;
#include <iomanip>
int maze[10][10]={
{0, 0, 0, 0,-1, 0, 0, 0, 0, 0},
{0,-1,-1, 0, 0, 0, 0,-1, 0, 0},
{0, 0,-1, 0,-1, 0, 0,-1, 0,-1},
{0, 0,-1, 0,-1, 0, 0,-1, 0,-1},
{0, 0, 0, 0,-1,-1, 0,-1, 0, 0},
{0,-1, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0,-1, 0, 0, 0,-1, 0,-1},
{-1,0, 0,-1, 0, 0, 0,-1, 0,-1},
{0, 0, 0, 0, 0, 0, 0, 0, 0,-1}
};
int way[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int road[100][4]={0};
void print(int m[][10])
{for (int i=0;i<10;i++)
{for (int j=0;j<10;j++)
cout<<setw(3)<<m[i][j];
cout<<endl;
}
cout<<endl;
}
int check(char t[])
{int m,n;
m=t[0]-48-1,n=t[2]-48-1;
if (m<0||m>9||n<0||n>9||t[1]!=','||maze[m][n]==-1)
return 1;
return 0;
}
int screen(int m[][10])
{for(int i=0;i<10;i++)
{for (int j=0;j<10;j++)
if (m[i][j]==0)
return 1;
}
return 0;
}
void handlers(int r,int c)
{int d,p=0,row,flag=1,col,r_next,c_next;
row=r;col=c;
maze[row][col]=1;
while (screen(maze))
{p++;
for(int i=0;i<10;i++)
{for (int j=0;j<10;j++)
if (maze[i][j]==p)
{d=0;
while (d<4)
{r_next=i+way[d][0];
c_next=j+way[d][1];
if (r_next<0||r_next>9||c_next<0||c_next>9||maze[r_next][c_next]==-1||maze[r_next][c_next]!=0)
d++;
else
maze[r_next][c_next]=p+1;
}
}
}
}
}
void show(int p,int q,int val)
{int endr,endc,k;
endr=p,endc=q,k=val;
for (int i=0;i<k;i++)
{for (int j=0;j<k;j++)
if (maze[i][j]>=k)
if ((i==endr&&j!=endc)||(j==endc&&i!=endr)||(i!=endr&&j!=endc))
maze[i][j]=0;
else
continue;
}
}
void writer_zero(int r,int c)
{int d,m,n,p,endr,endc;
endr=r,endc=c;
p=maze[endr][endc];
while (p>1)
{p--;
for (int i=0;i<10;i++)
{for (int j=0;j<10;j++)
if (maze[i][j]==p)
{d=0;
while (d<4)
{m=i+way[d][0];
n=j+way[d][1];
if (m<0||m>9||n<0||n>9||maze[m][n]==-1||maze[m][n]<p)
d++;
if (maze[m][n]-1==p)
break;
}
if (d!=4)
continue;
else
maze[i][j]=0;
}
}
}
print(maze);
}
void print_path(int m,int r[][4],int p,int q)
{cout<<setw(2)<<maze[p][q]<<setw(3)<<"("<<p+1<<","<<q+1<<")"<<endl;
for (int k=m-1;k>=0;k--)
cout<<setw(2)<<r[k][0]<<setw(3)<<"("<<r[k][1]+1<<","<<r[k][2]+1<<")"<<endl;
cout<<endl;
}
void print_r(int m)
{for (int i=0;i<=m;i++)
cout<<setw(3)<<road[i][0]<<setw(2)<<"("<<road[i][1]+1<<","<<road[i][2]+1<<")"<<endl;
cout<<endl;
}
int path(int r,int c,int e,int f)
{int i,j,flag=1,step=0,d,row,col,endr,endc;
row=r,col=c,endr=e,endc=f;
road[step][0]=maze[row][col];
road[step][1]=row;
road[step][2]=col;
road[step][3]=0;
while (maze[endr][endc]!=road[step][0])
{d=road[step][3];
while (d<4&&flag)
{if (road[step][0]==maze[endr][endc])
{ road[step][0]=maze[endr][endc];
road[step][1]=i;
road[step][2]=j;
road[step][3]=-1;
flag=0;
}
else
{i=road[step][1]+way[d][0];
j=road[step][2]+way[d][1];
if (maze[i][j]==-1||maze[i][j]==0||i<0||i>9||j<0||j>9||maze[i][j]<maze[road[step][1]][road[step][2]])
d++;
else
{road[step][3]=d;
road[step+1][0]=maze[i][j];
road[step+1][1]=i;
road[step+1][2]=j;
step++;
d=road[step][3];
}
}
}
}
return step;
}
void path_all(int end)
{int p,i,j,d,m,n,ordinal,c=1;
p=end-1;
while (p>=0)
{d=road[p][3]+1;
while(d<4)
{m=road[p][1]+way[d][0];
n=road[p][2]+way[d][1];
if (maze[m][n]!=road[p+1][0])
d++;
else
{road[p][3]=d;
road[p+1][1]=m;
road[p+1][2]=n;
ordinal=p+1;
while (ordinal<end)
{d=0;
while (d<4)
{i=road[ordinal][1]+way[d][0];
j=road[ordinal][2]+way[d][1];
if (maze[i][j]==road[ordinal+1][0])
{road[ordinal][3]=d;
road[ordinal+1][1]=i;
road[ordinal+1][2]=j;
ordinal++;
break;
}
else
d++;
}
}
p=end;
cout<<"迷宫第"<<++c<<"条最短路径为:\n";
print_r(end);
break;
}
}
p--;
}
}
void main()
{int p,total,startr,startc,endr,endc;
char a[3];
print(maze);
cout<<"请输入起点坐标以逗号间隔例如:6,5"<<endl;
cin>>a;
while(check(a))
{cout<<"请重新输出入起点坐标:\n";
cin>>a;
}
startr=a[0]-48-1,startc=a[2]-48-1;
cout<<"请输入终点坐标以逗号间隔例如:1,1"<<endl;
cin>>a;
while(check(a))
{cout<<"请重新输出入终点坐标:\n";
cin>>a;
}
endr=a[0]-48-1,endc=a[2]-48-1;
cout<<endl;
handlers(startr,startc);
p=maze[endr][endc];
show(endr,endc,p);
writer_zero(endr,endc);
total=path(startr,startc,endr,endc);
cout<<"迷宫第1条最短路径为:\n";
print_r(total);
path_all(total);
}
您所在位置：
GCC
[专家分：14380] 发布于 2006-04-14 11:53:00 
