SDNU 1086.迷宫问题（bfs标记路径）

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)

#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define ll long long

int f[8][8], ii = 0;

struct node
{
    int x, y;
};

struct edge//记录每个点
{
    int x, y;
}e[8][8];

int path[4][2] = {0,1, 0,-1, 1,0, -1,0};

void bfs()
{
    queue<node>q;
    node p;
    p.x = 0;
    p.y = 0;
    q.push(p);
    while(!q.empty())
    {
        node l = q.front();
        q.pop();
        if(l.x == 4 && l.y == 4)return;
        for(int i = 0; i<4; i++)
        {
            node w;
            w.x = l.x+path[i][0];
            w.y = l.y+path[i][1];
            if(w.x >= 0 && w.y >= 0 && w.x<5 && w.y<5 && !f[w.x][w.y])
            {
                f[w.x][w.y] = 1;
                e[w.x][w.y].x = l.x;//记录该点的上一个点，因为上一个点是确认的
                e[w.x][w.y].y = l.y;//记录该点的上一个点，因为上一个点是确认的
                q.push(w);
            }
        }
    }
}

void print(int a, int b)
{
    if(a == 0 && b == 0)
    {
        printf("(0, 0)
");
        return;
    }
    print(e[a][b].x, e[a][b].y);
    printf("(%d, %d)
", a, b);
}

int main()
{
    for(int i = 0; i<5; i++)
        for(int j = 0; j<5; j++)
            scanf("%d", &f[i][j]);
    f[0][0] = 1;
    bfs();
    print(4, 4);
    return 0;
}