POJ3984（迷宫问题）

定义一个二维数组：


int maze[5][5] = {

	0, 1, 0, 0, 0,

	0, 1, 0, 1, 0,

	0, 0, 0, 0, 0,

	0, 1, 1, 1, 0,

	0, 0, 0, 1, 0,

};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

Input

一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。

Output

左上角到右下角的最短路径，格式如样例所示。

Sample Input

Sample Output

(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

#include <iostream>
#include<string.h>
#include<algorithm>
using namespace std; 
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int flag[10]={0};
long long ans,m;
char str[10][10];
int n,k;
#define QSize 50
int a[5][5];
int dis[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
struct Node{
    int x,y,pre;
}queue[QSize];//设置一个50个格子的队列 
int front=0;
int rear=0;//设置队头和队尾，头指针指向头元素,尾指针指向队尾的下一个位置  
int visit[5][5];//记录是否访问过的数组
//广度优先遍历
void bfs(int beginX,int beginY,int endX,int endY)
{
    queue[0].x =beginX,queue[0].y =beginY,queue[0].pre =-1;
    rear=rear+1;
    visit[beginX][beginY]=1;
    while(front<rear)//如果队列不为空 
    {
        for(int i=0;i<4;i++)
        {
            int newx=queue[front].x +dis[i][0];
            int newy=queue[front].y +dis[i][1];
            if(newx<0||newx>5||newy<0||newy>5||a[newx][newy]==1||visit[newx][newy]==1)
             continue;
             //进队
             queue[rear].x =newx;
             queue[rear].y =newy;
              queue[rear].pre =front;
              rear++;
              visit[newx][newy]=1;//给走过的位置标记
               if(newx==endX&&newy==endY)
               return; 
        }
        front++;//出队 
    }
 } 
 void print(Node now){
     if(now.pre ==-1)
     cout<<"("<<now.x <<","<<now.y <<")"<<endl;
     else{
         print(queue[now.pre ]);
         cout<<"("<<now.x <<","<<now.y <<")"<<endl;
     }
 }
int main()
{
    int maze[5][5];
    for(int i=0;i<5;i++)
    {
        for(int j=0;j<5;j++)
        {
            cin>>a[i][j];
        }
    }
    bfs(0,0,4,4);
    print(queue[rear-1]);
/*    for(int i=0;i<rear;i++)
    {
        cout<<"("<<queue[i].x <<","<<queue[i].y <<")"<<endl;
    }*/
    return 0;
}