回溯法迷宫问题

迷宫问题
 1 #include <iostream>
 2 using namespace std;
 3 
 4 int flag = 0;
 5 const int m = 5;
 6 const int n = 5;
 7 int a[m][n] = {
 8         {0,0,0,1,1},
 9         {1,0,0,0,0},
10         {0,1,1,0,1},
11         {1,0,0,0,0},
12         {0,1,0,1,0}
13     };
14 void search(int x,int y)
15 {
16     if((x==m-1)&&(y==n-1))         //当到达出口时，设置标志为1
17         flag = 1;
18     else 
19     {
20         a[x][y] = 1;
21         if( (!flag) && (y!=n-1) && (a[x][y+1]==0) )  search(x,y+1);  //向右走
22         if( (!flag) && (x!=m-1) && (a[x+1][y]==0) )  search(x+1,y);  //向下走
23         if( (!flag) && (y!=0) && (a[x][y-1]==0) )  search(x,y-1);    //向左走
24         if( (!flag) && (x!=0) && (a[x-1][y]==0) )  search(x-1,y);    //向上走
25     }
26     a[x][y] = 0;
27     if(flag == 1)              //因为标志为全局变量，故找到出口后，将根据标志位(flag=1)在回溯时用7来设置目标通路
28         a[x][y]=7;
29 }
30 
31 int main()
32 {
33     int i,j;
34 
35     cout<<"迷宫地图(0表示通路):"<<endl;
36     for(i=0;i<m;i++)
37     {
38         for(j=0;j<n;j++)
39             cout<<a[i][j];
40         cout<<endl;
41     }
42     cout<<endl;
43 
44     search(0,0);
45 
46     cout<<"迷宫出路(由7表示):"<<endl;
47     for(i=0;i<m;i++)
48     {
49         for(j=0;j<n;j++)
50             cout<<a[i][j];
51         cout<<endl;
52     }
53     return 0;
54 }
continue my dream...