?

測試代碼:

? 1?? 0?? 0?? 0?? 0?? 0?? 1?? 0
? 0?? 1?? 1?? 0?? 0?? 0?? 1?? 0
? 0?? 0?? 1?? 0?? 1?? 0?? 1?? 0
? 0?? 1??-1?? 0?? 1?? 0?? 0?? 0
? 0?? 1?? 0?? 1?? 0?? 1?? 1?? 0
? 0?? 0?? 1?? 0?? 0?? 1?? 0?? 0
? 1?? 0?? 1?? 0?? 0?? 1?? 0?? 1
? 0?? 0?? 1?? 0?? 0??-2?? 0?? 0

?1代表障礙，0代表能走通，-1代表入口 2代表出口路徑?
本題我使用的是遞歸調用的方法解決的，
是一種深收的算法，呵呵！！！廢話不多說，看哥的
精彩程序吧！！！

?

這里 0代表能走通，1代表障礙，2代表通道，3代表起始點和終止點
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#define INT_SIZE 1000
using namespace std;

?

int a[100][100];//聲明數組，用來存每個坐標
int path[100];//聲明數組，用來存放通道路徑
int n=0,k=0;//標記作用

?

int Find(int i1,int j1,int line1,int rows1)//遞歸程序
{
? int i,j,line,rows,mark=0;
?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;
?
? else
? {??
?? a[i][j]=5;
? if(i==0&&j==0&&mark!=1)//左上角
?? {
??? if(Find(i+1,j,line,rows)==1)
???? n=1;
?? else
??? if(Find(i,j+1,line,rows)==1)
???? n=1;
?????? if(n>0)
??? {
???? path[k]=i*rows+j;
???? k++;
?? return k;
??? }
??? mark=1;
???
? }
??
??
??
??
??
?????? if(i==0&&j==rows-1&&mark!=1)//右上角
?? {
???
???? if(Find(i,j-1,line,rows)==1)
???? n=1;
?????? else if(Find(i+1,j,line,rows)==1)
???? n=1;
????????? if(n>0)
??? {
???? path[k]=i*rows+j;
???? k++;
??? return k;
??? }
?? mark=1;
??
?? }
?
??
??
??
??
??
??
?? if(i==line-1&&j==0&&mark!=1)//左下角
??{
???
??? if(Find(i-1,j,line,rows)==1)
???? n=1;
??? else if(Find(i,j+1,line,rows)==1)
???? n=1;
???if(n>0)
??? {
???? path[k]=i*rows+j;
???? k++;
??? return k;
???? }
?? mark=1;
??
???
??}
??
??
??
??
?? if(i==line-1&&j==rows-1&&mark!=1)//右下角
?? {
??? if(Find(i,j-1,line,rows)==1)
???? n=1;
?? else if(Find(i-1,j,line,rows)==1)
???? n=1;
??? if(n>0)
??? {
???? path[k]=i*rows+j;
???? k++;
??? return k;
??? }
?? mark=1;
??
?? }

?

?? if(i==0&&mark!=1)//上邊界
????? {?
??? if(Find(i,j-1,line,rows)==1)
???? n=1;
??? else
??? {
???? if(Find(i,j+1,line,rows)==1)
???? n=1;
??????? else if(Find(i+1,j,line,rows)==1)
???? n=1;
??? }
??? if(n>0)
??? {
???? path[k]=i*rows+j;
???? k++;
??? return k;
??? }
?? mark=1;
??
?? }
??
??
??
??
?? if(j==0&&mark!=1)//左邊界
????? {
??? if(Find(i-1,j,line,rows)==1)
???? n=1;
??? else
??? {
???? if(Find(i+1,j,line,rows)==1)
???? n=1;
??? else if(Find(i,j+1,line,rows)==1)
???? n=1;
??? }
??? if(n>0)
??? {
???? path[k]=i*rows+j;
???? k++;
???? return k;
??? }
?? mark=1;
??
?? }
??
??
??
?? if(i==line-1&&mark!=1)//下邊界
????? {
??? if(Find(i,j-1,line,rows)==1)
???? n=1;
??? else
??? {
???? if(Find(i,j+1,line,rows)==1)
???? n=1;
??? else if(Find(i-1,j,line,rows)==1)
???? n=1;
??? }
??? if(n>0)
??? {
???? path[k]=i*rows+j;
???? k++;
??? return k;
??? }
?? mark=1;
??
?? }

?

?? if(j==rows-1&&mark!=1)//右邊界
????? {
??? if(Find(i-1,j,line,rows)==1)
???? n=1;
?? else
?? {
??? if(Find(i+1,j,line,rows)==1)
???? n=1;
??? else if(Find(i,j-1,line,rows)==1)
???? n=1;
?? }
??? if(n>0)
??? {
???? path[k]=i*rows+j;
???? k++;
??? return k;
??? }
?? mark=1;
??

?? }

?

?????? if(mark!=1)//普通點
??? {
??? if(Find(i-1,j,line,rows)==1)
???? n=1;
??? else
??? {
??? if(Find(i+1,j,line,rows)==1)
???? n=1;
??? else
??? {
???? if(Find(i,j-1,line,rows)==1)
???? n=1;
???
??? else if(Find(i,j+1,line,rows)==1)
??????????? n=1;
??? }

??? }
??? if(n>0)
??? {
???? path[k]=i*rows+j;
???? k++;
??????? return k;
??? }
???? mark=1;
??? }
???
? }

return 0;
}
???
????????

??????????????

int main()
{
?int line,rows,i,j,starti,startj,endi,endj;
?printf("歡迎使用本迷宮求解系統\n");
?printf("---------------------------------------------------\n");
?printf("請輸入迷宮的行數和列數:\n");
??? cin>>line>>rows;
?memset(a,0,sizeof(a));
?memset(path,-1,sizeof(path));
?printf("請輸入障礙點坐標的個數:\n");
?int num,m;
?cin>>num;
??? m=num;
?while(m--)
?{
??printf("請輸入第%d個障礙點的坐標:\n",num-m);
??????? cin>>i>>j;
??a[i][j]=1;
?}

?printf("請輸入迷宮起始點的坐標:\n");
?????? cin>>starti>>startj;
??? a[starti][startj]=-1;
?printf("請輸入迷宮出口點的坐標:\n");
??? cin>>endi>>endj;
??? a[endi][endj]=-2;
??? i=starti;
??? j=startj;
?if(Find(i,j,line,rows)>0)
??{
??cout<<"Great"<<endl;
??? ?for(k=0;path[k]!=-1;k++)
??{
???i=path[k]/rows;
???j=path[k]%rows;
???a[i][j]=2;
??}
??a[starti][startj]=3;
??a[endi][endj]=3;
???? 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
???? cout<<"由于您輸入錯誤，此迷宮沒有出路"<<endl;
?????????????????????????????????
??? return 0;
}

?

總結

以上是生活随笔為你收集整理的迷宫求解无敌版(递归调用法)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。