POJ - 3984 迷宫问题

打印路径的迷宫问题，根据bfs来说，队尾是由队首得到的，所以我们只需要加一个映射，让队尾映射到队首。用函数提供的queue函数比较法麻烦，需要建立指针，所以自己手撕了一个队列，用l和r表示边界，代码如下

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <map>
#include <cstdio>

using namespace std;

int l = 0, r = 0;
int used[10][10];
int M[10][10];
int flag[500];
int cx[4] = {0, 0, -1, 1},
    cy[4] = {1, -1, 0, 0};

struct ll{
    int x, y;
};

map<int, ll> p;

bool check(int x, int y)
{
    if(x >= 0 && x < 5 && y >= 0 && y < 5 && !used[x][y] && M[x][y] == 0)
        return 1;
    return 0;
}

void BFS()
{
    ll f, s;
    f.x = 0;
    f.y = 0;
    p[r] = f;
    while(l <= r) {
        f = p[l];
        if(f.x == 4 && f.y == 4) {
            break;
        }
        for(int i = 0; i < 4; i++) {
            s.x = f.x + cx[i];
            s.y = f.y + cy[i];
            if(check(s.x, s.y)) {
                p[++r] = s;
                flag[r] = l;
                used[s.x][s.y] = 1;
            }
        }
        l++;
    }
}

void ANS(int t)
{
    if(flag[t])
        ANS(flag[t]);
    printf("(%d, %d)\n", p[t].x, p[t].y);
}

int main()
{
    for(int i = 0; i < 5; i++) {
        for(int j = 0; j < 5; j++) {
            cin >> M[i][j];
        }
    }
    BFS();
    printf("(0, 0)\n");
    ANS(l);
    return 0;
}