POJ – 3984 迷宫问题 【BFS】

题目链接

http://poj.org/problem?id=3984

思路

因为要找最短路 用BFS

而且 每一次 往下一层搜 要记录当前状态 之前走的步的坐标

最后 找到最短路后 输出坐标就可以了

AC代码

#include <cstdio>
#include <cstring>
#include <ctype.h>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <stack>
#include <set>
#include <numeric>
#include <sstream>
#include <iomanip>
#include <limits>#define CLR(a) memset(a, 0, sizeof(a))
#define pb push_backusing namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair<string, int> psi;
typedef pair<string, string> pss;const double PI = acos(-1);
const double E = exp(1);
const double eps = 1e-30;const int INF = 0x3f3f3f3f;
const int maxn = 5e4 + 5;
const int MOD = 1e9 + 7;int G[5][5];
int v[5][5];int Move[4][2]
{
    -1, 0,
     1, 0,
     0,-1,
     0, 1,
};struct Node
{
    int x, y;
    vector <pii> ans;
}tmp;vector <pii> ans;queue <Node> q;bool ok(int x, int y)
{
    if (x < 0 || x >= 5 || y < 0 || y >= 5 || v[x][y] || G[x][y])
        return false;
    return true;
}void bfs()
{
    tmp.x = 0;
    tmp.y = 0;
    tmp.ans.pb(pii(0, 0));
    v[tmp.x][tmp.y] = 1;
    q.push(tmp);
    while (!q.empty())
    {
        int x = q.front().x;
        int y = q.front().y;
        ans = q.front().ans;
        q.pop();
        if (x == 4 && y == 4)
            return;
        for (int i = 0; i < 4; i++)
        {
            tmp.x = x + Move[i][0];
            tmp.y = y + Move[i][1];
            if (ok(tmp.x, tmp.y))
            {
                tmp.ans = ans;
                tmp.ans.pb(pii(tmp.x, tmp.y));
                q.push(tmp);
                tmp.ans.pop_back();
                v[tmp.x][tmp.y] = 1;
            }
        }
    }}int main()
{
    CLR(v);
    for (int i = 0; i < 5; i++)
    {
        for (int j = 0; j < 5; j++)
            scanf("%d", &G[i][j]);
    }
    bfs();
    vector <pii>::iterator it;
    for (it = ans.begin(); it != ans.end(); it++)
    {
        printf("(%d, %d)\n", (*it).first, (*it).second);
    }
}