欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

18276 走迷宫

程序员文章站 2022-05-24 09:34:42
...

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;
    }
}
相关标签: 广度搜索