Problem 2285 迷宫寻宝

http://acm.fzu.edu.cn/problem.php?pid=2285

Problem Description

洪尼玛今天准备去寻宝，在一个n*n （n行, n列）的迷宫中，存在着一个入口、一些墙壁以及一个宝藏。由于迷宫是四连通的，即在迷宫中的一个位置，只能走到与它直接相邻的其他四个位置（上、下、左、右）。现洪尼玛在迷宫的入口处，问他最少需要走几步才能拿到宝藏？若永远无法拿到宝藏，则输出-1。

Input

多组测试数据。

每组数据输入第一行为正整数n，表示迷宫大小。

接下来n行，每行包括n个字符，其中字符'.'表示该位置为空地，字符'#'表示该位置为墙壁，字符'S'表示该位置为入口，字符'E'表示该位置为宝藏，输入数据中只有这四种字符，并且'S'和'E'仅出现一次。

n≤1000

Output

输出拿到宝藏最少需要走的步数，若永远无法拿到宝藏，则输出-1。

Sample Input

5 S.#.. #.#.# #.#.# #...E #....

Sample Output

代码：

#include <iostream>

#include <stdio.h>

#include <queue>

#include <algorithm>

#include <string.h>

#include <cstdio>

using namespace std;

int N;

int sx, sy, ex, ey;

char mp[1010][1010];

int vis[1010][1010];

int dx[5] = {0, 1, 0, -1};

int dy[5] = {1, 0, -1, 0};

bool flag = false;

void bfs(int x, int y) {

    queue<pair<int, int> > q;

    pair<int, int> r;

    r.first = x;

    r.second = y;

    q.push(r);

    while(!q.empty()) {

        pair<int, int> p = q.front();

        q.pop();

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

            pair<int, int> now;

            now.first = p.first + dx[i];

            now.second = p.second + dy[i];

            if(vis[now.first][now.second] || now.first < 1 || now.first > N

               || now.second < 1 || now.second > N

               || mp[now.first][now.second] == '#') continue;

            vis[now.first][now.second] = vis[p.first][p.second] + 1;

            q.push(now);

        }

        if(vis[ex][ey]) {

            flag = true;

            break;

        }

    }

}

int main() {

    while(~scanf("%d", &N)) {

        for(int i = 1; i <= N; i ++)

            scanf("%s", mp[i] + 1);

        memset(vis, 0, sizeof(vis));

        flag=false;

        for(int i = 1; i <= N; i ++) {

            for(int j = 1; j <= N; j ++) {

                if(mp[i][j] == 'S') {

                    sx = i;

                    sy = j;

                } else if(mp[i][j] == 'E') {

                    ex = i;

                    ey = j;

                }

            }

        }

        bfs(sx, sy);

        if(flag) printf("%d\n", vis[ex][ey]);

        else printf("-1\n");

    }

    return 0;

}

秒客网