/********************************

 啊哈！算法

 深度优先搜索算法

 迷宫问题

 输入：

 5 4

 0 0 1 0

 0 0 0 0

 0 0 1 0

 0 1 0 0

 0 0 0 1

 1 1 4 3

 输出：7

 *********************************/

 #include<iostream>

 #include<ctime>

 using namespace std;

 int count=;

 int endx,endy,m,n;

 void dfs(int **pos,bool **book,int sx,int sy,int step,int &min)

 {

     if(sx==endx && sy==endy)

     {

         if(step<=min)

             min=step;

         cout<<"第"<<count++<<"方案："<<step<<endl;

         return;//出口

     }

     int move[][]={

         {,},

         {,-},

         {,},

         {-,}

     };

     int tx,ty;

     for(int i=;i<;i++)

     {

         tx=sx+move[i][];

         ty=sy+move[i][];

         if(tx>m || tx< || ty>n || ty<)

             continue;

         if(pos[tx][ty]== && book[tx][ty]==)

         {

             book[tx][ty]=true;

             dfs(pos,book,tx,ty,step+,min);

             book[tx][ty]=;//**尝试结束，取消这个点的标记

         }

     }

 }

 int main()

 {

     int i,j;

     cout<<"输入迷宫的行列：";

     cin>>m>>n;

     int **pos=new int *[m+];//迷宫。指针数组

     bool **book=new bool*[m+];//记录是否走过

     for(i=;i<m+;i++)

     {

         pos[i]=new int[n+];

         book[i]=new bool[n+];

     }

     cout<<"输入迷宫(1表示障碍物，0表示通道,空格隔开)："<<endl;

     for(i=;i<m+;i++)

     {

         for(j=;j<n+;j++)

         {

             cin>>pos[i][j];

             while(!cin.good())

             {

                 cin.clear();

                 while(cin.get()!='\n')

                     continue;

                 cout<<"在第"<<i+<<"行"<<"第"<<j+<<"列"<<"输入错误"<<endl;

                 cout<<"重新输入："<<endl;

                 cin>>pos[i][j];

             }

         }

     }

     cout<<endl<<"迷宫："<<endl;

     for(i=;i<m+;i++)

     {

         for(j=;j<n+;j++)

             cout<<pos[i][j]<<" ";

         cout<<endl;

     }

     for(i=;i<m+;i++)

         for(j=;j<n+;j++)

             book[i][j]=;

     int startx,starty;

     cout<<"输入起始点: ";

     cin>>startx>>starty;

     book[startx][starty]=true;

     cout<<"输入终点: ";

     cin>>endx>>endy;

     int step=,min=;

     dfs(pos,book,startx,starty,step,min);

     if (min<)

         cout<<"最短步数是: "<<min<<endl;

     else cout<<"不存在路径"<<endl;

     for(i=;i<m+;i++)

     {

         delete [] pos[i];

         delete [] book[i];

     }

     delete [] pos;

     delete [] book;

     return ;

 }

 /**********************

 BFS

 *************/

 #include<iostream>

 using namespace std;

 struct node

 {

     int x;

     int y;

     int f;//记录路径

     int s;//记录步长

 };

 struct stack

 {

     int st[];

     int top;

 };

 int main()

 {

     node queue[];

     bool book[][]={false};

     int m,n,sx,sy,ex,ey;

     cout<<"row and column:";

     cin>>m>>n;

     int i,j;

     int **pos=new int*[m+];

     for(i=;i<m+;i++)

         pos[i]=new int[n+];

     cout<<"screat map:"<<endl;

     for(i=;i<m+;i++)

         for(j=;j<n+;j++)

             cin>>pos[i][j];

     cout<<"start and end:";

     cin>>sx>>sy>>ex>>ey;

     book[sx][sy]=;

     int head=, tail=;

     queue[head].x=sx;  //定义后初始化只能以这种方式,出发点

     queue[head].y=sy;

     queue[head].f=head;

     queue[head].s=;

     tail++;//tail超前队列最后一个元素一位

     int move[][]={

         {,},{-,},{,-},{,}

     };

     int goal=;

     while(head!=tail)

     {

         if( queue[head].x==ex && queue[head].y==ey)

         {

             goal=head;

             cout<<"最短路径:"<<queue[head].s<<endl;

             head++;

             break; //广度优先搜索最先找到的就是最短的

         }

         for(i=;i<;i++)

         {

             node t={queue[head].x+move[i][],queue[head].y+move[i][],head,queue[head].s+};

             //遍历四个方向如果合法且没被标记则入队

             if(t.x>m || t.x< || t.y>n || t.y<)

                 continue;

             if(pos[t.x][t.y]== && book[t.x][t.y]==false)

             {

                 queue[tail]=t;//结构体可整体复制

                 tail++;

                 book[t.x][t.y]=true;//注意走过的路要标记

             }

         }

         head++;

     }

     //打印路径

     cout<<"队列中的位置是："<<endl;

     i=goal;cout<<goal<<endl;

     stack re={{},};

     while(queue[i].s>=)//直到回溯到起始点

     {

         re.st[re.top++]=i;//反着从终点到起点入栈

         i=queue[i].f;//这里错了，不要i--，i记录上一个位置的前任(在队列中的位置)

         if(i==)//起始点的前任是它自己，要标记退出，不然死循环

             break;

     }

     while(re.top>=)

     {

         cout<<queue[re.st[re.top]].x<<" "<<queue[re.st[re.top]].y;//先进后出，出栈，正着打印

         if(re.top!=)

             cout<<"->";

         re.top--;

     }

     cout<<endl;

     for(i=;i<m+;i++)

         delete [] pos[i];

     delete [] pos;

     return ;

 }