迷宫问题–POJ3984
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 22008 Accepted: 12848
Description

定义一个二维数组：

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

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
Sample Output

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

CE–4次，PE–2次.

#include<iostream>

#include<queue>

#include<cstdio>

#include<cstdlib>

#include<string>

#define N 5                 //迷宫长度

#define M 5                 //迷宫宽度

using namespace std;

int maze[N][M];

typedef struct point

{

    int x;

    int y;

    point *previous;

    int step;

}point;

int sx = 0, sy = 0;         //起点

int gx = 4, gy = 4;         //终点

int dir[4][2] = {           //方向

    {0,1},{1,0},            //上，右

    {0,-1},{-1,0}           //下，左

};

void show(point *p)         //逆向输出链表

{

    if (p != NULL)

    {

        show(p->previous);

        cout << "(" << p->x << ", " << p->y << ")" << endl;

    }

}

void BFS(point start)

{

    queue<point> q;

    q.push(start);               //把头节点放入队列

    point current,next;

    while (!q.empty())

    {

        current = q.front();     // 记录当前节点

        q.pop();                 //弹出元素

        maze[current.x][current.y] =1；

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

        {

            /*此处本来可以使用next{ current.x + dir[i][0],current.y + dir[i][1],NULL,0 };这样的写法，但是poj不认，所以退而求其次，用下面这种写法*/

            next.x=current.x + dir[i][0];

            next.y=current.y + dir[i][1];

            next.previous=NULL;

            next.step=0 ;

            if (next.x >= 0 && next.x < N&&next.y >= 0 && next.y < M&&maze[next.x][next.y] ==0)                //判断这个点是否合乎要求，即在迷宫数组内，但是又不是墙，并且没有被标记过

            {

                point *tmp = new point;                         //申请空间

                memcpy(tmp, &current, sizeof(point));           //复制地址

                next.previous = tmp;

                //next.step = current.step + 1;                //如果需要记录路径的话，就加上这一句

                maze[next.x][next.y] = 1;                      //表示这个点已经被搜索过了，所以标记

                    if (next.x == gx &&next.y==gy)//如果发现到了终点，那么就输出路径

                {

                    show(&next);

                    return;

                }

                q.push(next);          //将下一个点加入队列

            }

        }

    }

}

int main(void)

{

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

        for (int j = 0; j <= 4; ++j)

            cin >> maze[i][j];

    point start;

    start.x=0;

    start.y=0,start.previous=NULL;

    start.step=0;

    BFS(start);

    return 0;

}

这里主要是记录路径比较麻烦，如果不考虑这个，就是一道简单的BFS题，对于BFS，需要将题目抽象成一副图，包含对应的节点和对应的边，在这里，节点就是迷宫的每个点，如果两个点之间是联通的话，那么可以认为两个节点之间建立了一条边，而对于迷宫而言，就是一个无权图，或者说是个权重为1的有权图，通过广搜就可以获得起路径，而BFS是否一定会获得最短路径，这个是一定的。

http://blog.csdn.net/raphealguo/article/details/7523411

这个作者讲的很清楚，我也是从中得到启发。