蓝桥云课 Problem.141 穿越雷区

发布于 2024-03-09  339 次阅读

原链: https://www.lanqiao.cn/problems/141/learning/

一、题目

（1）题目描述

X 星的坦克战车很奇怪，它必须交替地穿越正能量辐射区和负能量辐射区才能保持正常运转，否则将报废
某坦克么需要从A区到B区去（A，B 区本身是安全区，没有正能量或负能量特征），怎么样走才能路径最短？
已知的地图是一个方阵，上面用字母标出了 A，B 区，其他区都标了正号或负号分别表示正负能力辐射区
例如：

5
A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -

坦克车只能水平或垂直方向上移动到相邻的区域

（2）输入描述

第一行是一个整数 n，表示方阵的大小，4 ≤ n ＜ 100
接下来是 n 行，每行有 n 个数据，可能是 A，B，+，- 中的某一个，中间用空格分开
A，B 都只出现一次

（3）输出描述

输出一个整数，表示坦克从A区到B区的最小移动步数
如果没有方案，则输出 -1

（4）样例

输入

A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -

输出

10

二、思路

本题本人在解题过程中参考了 蓝桥云课@鲸狸 的题解

本题通使用广度优先搜索寻找从起点“A”至终点“B”的最短路径
此处我们只关注主要的推理：
程序需要2个二维数组，map 储存地图数组，path 储存路径，和一个ArrayList，存储可能的路径
每走一步，我们需要在将当前位置在 path 数组中标记为已走过，并就上下左右的四个格子的情况，构造一个MapPaths对象（原题解作者用的是Python中的元组Tuple，Java也有，这里为了代码可读性就自己构造对象了）存入ArrayList待程序检查
上下左右格子需要满足以下条件才能作为待探索的区域

  1. （X，Y）没有越界
  2. 在 path 二维数组中未被标注探索过
  3. 能量值与上一个格子不同（即上一个格子为“+”正能量，那么下一个必须是“-”负能量）

当下一个格子的内容是“B”时候，我们可以认为我们抵达了终点，如果我们没有抵达终点（即ArrayList待查找队列空了）则程序返回 -1

三、代码

import java.util.*;
public class Problem141 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int x = in.nextInt();
        in.nextLine();
        String[][] map = new String[x][x];
        boolean[][] path = new boolean[x][x];
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < x; j++)
                map[i][j] = in.next();
        }

        for (int i = 0; i < x; i++) {
            for (int j = 0; j < x; j++)
                if (map[i][j].equals("A"))
                    System.out.println(search(map, path, i, j, x));
        }
    }

    public static int search(String[][] map, boolean[][] path, int startX, int startY, int gridSize) {
        ArrayList<MapPaths> possiblePath = new ArrayList<>();
        MapPaths mp = new MapPaths(startX, startY, 0);
        possiblePath.add(mp);
        path[startX][startY] = true;
        while (!possiblePath.isEmpty()) {
            MapPaths current = possiblePath.remove(0);
            int x = current.x, y = current.y, steps = current.steps;
            if (map[x][y].equals("B"))
                return steps;

            // 找上下左右
            { // 上
                int offsetX = 0, offsetY = 1;
                int newX = x + offsetX, newY = y + offsetY;
                if (newX < gridSize && newY < gridSize && !path[newX][newY] && !map[x][y].equals(map[newX][newY])) {
                    path[newX][newY] = true;
                    possiblePath.add(new MapPaths(newX, newY, steps + 1));
                }
            }

            { // 下
                int offsetX = 0, offsetY = -1;
                int newX = x + offsetX, newY = y + offsetY;
                if (newX < gridSize && newY > -1 && newY < gridSize && !path[newX][newY] && !map[x][y].equals(map[newX][newY])) {
                    path[newX][newY] = true;
                    possiblePath.add(new MapPaths(newX, newY, steps + 1));
                }
            }

            { // 左
                int offsetX = -1, offsetY = 0;
                int newX = x + offsetX, newY = y + offsetY;
                if (newX > -1 && newX < gridSize && newY < gridSize && !path[newX][newY] && !map[x][y].equals(map[newX][newY])) {
                    path[newX][newY] = true;
                    possiblePath.add(new MapPaths(newX, newY, steps + 1));
                }
            }

            { // 右
                int offsetX = 1, offsetY = 0;
                int newX = x + offsetX, newY = y + offsetY;
                if (newX < gridSize && newY < gridSize && !path[newX][newY] && !map[x][y].equals(map[newX][newY])) {
                    path[newX][newY] = true;
                    possiblePath.add(new MapPaths(newX, newY, steps + 1));
                }
            }
        }
        return -1;
    }
}

class MapPaths {
    public int x;
    public int y;
    public int steps;

    public MapPaths(int x, int y, int steps) {
        this.x = x;
        this.y = y;
        this.steps = steps;
    }
}