18276 走迷宫

18276 走迷宫

时间限制:1000MS 代码长度限制:10KB
提交次数:0 通过次数:0

题型: 编程题 语言: G++;GCC;VC

Description

有一个N*M的格子迷宫，1代表该格子为墙，不能通过，0代表可以通过，另外，在迷宫中
有一些传送门，走到传送门的入口即会自动被传送到传送门的出口（一次传送算1步）。人在迷宫中可以尝试
上下左右四个方向移动。现在给定一个迷宫和所有传送门的出入口，以及起点和终点，
问最少多少步可以走出迷宫。如果不能走出迷宫输出“die”。

输入格式

该程序为多CASE，第1行为CASE的数量
每一个CASE，第1行为两个数N（行）和M（列）
然后N行每行M个数
之后是一个数W，为传送门的数量
之后每行一个传送门的入口坐标c1(行),r1(列)和出口坐标c2,r2
之后是起点坐标和终点坐标sc(行) sr(列) ec(行) er(列)

注：传送门出入口和起点坐标和终点坐标不会出现在墙的位置
所有数字不超过100

输出格式

如题

输入样例

2
4 3
011
011
110
110
1
1 0 2 2
0 0 3 2
2 2
01
10
0
0 0 1 1

输出样例

3
die

#define _CRT_SECURE_NO_WARNINGS
#include "stdio.h"
#include "stdlib.h"
#include "iostream"
#include <string.h>
#include <vector>
#include<algorithm>
#include<queue>
using namespace std;

//地图
char map[105][105];
//传送地图
int wx[105][105];
int wy[105][105];
//定义步数
int step[105][105] = { 0 };

int main(void) {
    ios::sync_with_stdio(0), cin.tie(0);
    int N, M, W;
    int bx, by, ex, ey;
    int flag;
    int addx[4] = { 1,-1,0,0 };
    int addy[4] = { 0,0,1,-1 };
    int nextx, nexty;
    int T;
    cin >> T;
    while (T--) {
        memset(step, 0, 105 * 105 * sizeof(int));
        memset(wx, 0, 105 * 105 * sizeof(int));
        memset(wy, 0, 105 * 105 * sizeof(int));
        cin >> N >> M;
        flag = 0;
        //输入地图
        for (int i = 0; i < N; i++)for (int j = 0; j < M; j++)cin >> map[i][j];
        //传送次数
        cin >> W;
        for (int i = 0; i < W; i++) {
            int x, y, a, b;
            cin >> x >> y >> a >> b;
            //传送标记为#
            map[x][y] = '#';
            //存储传送位置x  y
            wx[x][y] = a;
            wy[x][y] = b;
        }
        //输入起点  终点
        cin >> bx >> by >> ex >> ey;
        queue<int> stepx, stepy;
        int lastx, lasty, nextx, nexty;
        int flag = 0;
        //入队起点终点
        stepx.push(bx);
        stepy.push(by);

        //如果队列不为空持续循环
        while (!stepx.empty()) {
            //如果找到出口  标记 退出
            if (stepx.front() == ex && stepy.front() == ey) {
                flag = 1;
                break;
            }           
            //如果当前队头为传送点  就处理好步数传送然后不要判定四个方向，传送完直接出队
            else if (map[stepx.front()][stepy.front()]=='#') {
                nextx = wx[stepx.front()][stepy.front()];
                nexty = wy[stepx.front()][stepy.front()];
                //标记如果有障碍   该格子已被走过     越界   则直接出队这个传送点
                if (map[nextx][nexty] == '1' || step[nextx][nexty] != 0 || nextx < 0 || nextx >= N || nexty < 0 || nexty >= M) {
                    stepx.pop();
                    stepy.pop();
                    continue;
                }
                //标记好步数  为传送点的步数+1
                step[nextx][nexty] = step[stepx.front()][stepy.front()] + 1;
                //入队传送出口
                stepx.push(nextx);
                stepy.push(nexty);
            }
            //如果不为终点  也不为传送点  那就是普通点
            else {
                //判定四个方位的情况
                for (int i = 0; i < 4; i++)
                {
                    int curx, cury;
                    curx = stepx.front() + addx[i];
                    cury = stepy.front() + addy[i];
                    //如果不能走了就进入下一次循环
                    if (map[curx][cury] == '1' || step[curx][cury] != 0 || curx < 0 || curx >= N || cury < 0 || cury >= M) {
                        continue;
                    }
                    //如果没问题  入队
                    stepx.push(curx);
                    stepy.push(cury);
                    //标记步数
                    step[curx][cury] = step[stepx.front()][stepy.front()] + 1;
                }
            }
            //当前队头出队
            stepx.pop();
            stepy.pop();
        }
        //判定
        if (flag)cout << step[stepx.front()][stepy.front()] << endl; else cout << "die" << endl;
    }
}