poj 3984 迷宫问题

点击打开链接

迷宫问题

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

解题思路：

这是一个简单搜索，BFS，一般最短路问题都用BFS，千万不要用DFS啊，

其实搜索说难不难，说简单也不简单，当然这有点抽象就得需要自己仔细体会，

逐行逐行的看代码，其实习惯了也就会了，

下面上代码吧：

/*
2015 - 09 - 11 

Author: ITAK 

Motto:
今日的我要超越昨日的我，明日的我要胜过今日的我，
以创作出更好的代码为目标，不断地超越自己。
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int  map[10][10];
int dir[4][2] = {1,0,-1,0,0,1,0,-1};

struct node
{
    int x, y, pre;
} q[100];

void print(int x)///打印
{
    if(q[x].pre != -1)
    {
        print(q[x].pre);///回溯
        cout<<"("<<q[x].x<<", "<<q[x].y<<")"<<endl;
    }
}

void bfs(int x, int y)///广搜
{
    int rear=1, front=0;
    q[front].x = x, q[front].y = y;
    q[front].pre = -1;
    while(front < rear)
    {
        for(int i=0; i<4; i++)
        {
            int dx = q[front].x + dir[i][0];
            int dy = q[front].y + dir[i][1];///判断条件
            if(dx<0 || dx>=5 || dy<0 || dy>=5 || map[dx][dy])
                continue;
            map[dx][dy] = 1;///标记，表示已经走过
            q[rear].x = dx;
            q[rear].y = dy;
            q[rear].pre = front;
            rear++;///入队
            if(dx==4 && dy==4)
                print(front);
        }
        front++;///出队
    }
}
int main()
{
    for(int i=0; i<5; i++)
        for(int j=0; j<5; j++)
            cin>>map[i][j];
    cout<<"(0, 0)"<<endl;

    bfs(0,0);

    cout<<"(4, 4)"<<endl;
    return 0;
}