测试代码:
1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 0 0 0 1 1 1 2 0 1 0 1 1 1 0 1 0 0 1 1 0 1 0 -2 1 1 1 1 1 1 1 1 1
1代表障碍,0代表能通道,2代表起点,-2代表终点 本题我使用的是递归调用的方法解决的, 是一种深收的算法,呵呵!!!废话不多说,看哥的 精彩程序吧!!!
程序输入情况如下:
1代表障碍,2代表已经找到的通道,3代表起点和终点
#include<iostream>
#include<math.h>#include<stdio.h>#include<algorithm>#include<stdlib.h>#include<string.h>#define maxlength 100using namespace std; int a[maxlength][maxlength];int k=0;struct{
int line; int rows;}path[maxlength];//记录搜寻的路线
struct{
int line; int rows;}findpath[maxlength]={ {0,1}, {0,-1}, {1,0}, {-1,0}};//4个搜寻方向{0,1}右,{0,-1}左,{1,0}上,{-1,0}下
int FindPath(int i1,int j1,int line1,int rows1)
{ int i,j,line,rows; i=i1; j=j1; line=line1; rows=rows1; if(a[i][j]==-2) return 1; if(a[i][j]==1||a[i][j]==5) return 0; a[i][j]=5; for(int m=0;m<4;m++)//为了避免处理边界的问题,我们可以令迷宫的外围路径都是1, { i=i1+findpath[m].line; j=j1+findpath[m].rows; if(FindPath(i,j,line,rows)>0) { path[k].line=i; path[k].rows=j; k++; return k; } } return 0;}
int main()
{ int i,j,line,rows,n,m; int starti,startj,endi,endj; memset(a,0,sizeof(a)); printf("欢迎使用本迷宫求解系统\n"); printf("----------------------------------------------\n"); printf("请输入迷宫的行数\n"); cin>>line; printf("请输入迷宫的列数\n"); cin>>rows; for(i=0,j=0;i<line;i++) a[i][j]=1; for(i=0,j=0;j<rows;j++) a[i][j]=1; for(i=0,j=rows-1;i<line;i++) a[i][j]=1; for(i=line-1,j=0;j<rows;j++) a[i][j]=1; printf("请输入障碍点的个数\n"); cin>>n; m=n; while(m--) { printf("请输入输入第%d个障碍点的坐标\n",n-m); cin>>i>>j; a[i][j]=1; } printf("请输入起始点的坐标\n"); cin>>starti>>startj; a[starti][startj]=2; printf("请输入终止点的坐标\n"); cin>>endi>>endj; a[endi][endj]=-2; if(FindPath(starti,startj,line,rows)>0) { for(int m=0;m<k;m++) a[path[m].line][path[m].rows]=2; a[starti][startj]=3; a[endi][endj]=3; printf("求解后的迷宫如下图所示\n"); for(i=0;i<line;i++) { for(j=0;j<rows;j++) { if(a[i][j]==5) a[i][j]=0; cout<<a[i][j]<<" "; } cout<<endl; }}
else printf("抱歉,由于您输入错误,此迷宫没有通道\n");printf("----------------------------------------------\n"); return 0;}