机器人走迷宫问题

题目

1.房间有XY的方格组成，例如下图为64的大小。每一个方格以坐标(x,y) 描述。
2.机器人固定从方格(0, 0)出发，只能向东或者向北前进，出口固定为房间的最东北角，如下图的
方格(5,3)。用例保证机器人可以从入口走到出口。
3.房间有些方格是墙壁，如(4,1) ,机器人不能经过那儿。
4.有些地方是- -旦到达就无法走到出口的，如标记为B的方格，称之为陷阱方格。
5.有些地方是机器人无法达到的，如标记为A的方格，称之为不可达方格,不可达方格不包括墙壁
所在的位置
6.如下实例图中，陷阱方格有2个，不可达方格有3个。
7.请为该机器人实现路径规划功能:给定房间大小，墙壁位置，请计算出陷阱方格与不可达方格分别有多少个

输入
1.第一-行为房间的x和y(0 < x,y <= 1000 )
2.第二行为房间中墙壁的个数N (O <= N < x*Y)
3.接着下面会有N行墙壁的坐标

同一行中如果有多个数据以一个空格隔开，用例保证所有的输入数据均合法，(结尾不带回车换行

输出

1.陷阱方格与不可达方格数量，两个信息在一行中输出， 以一个空格隔开。(结尾不带回车换行)

Java代码

package day11;

import javax.print.attribute.standard.Chromaticity;
import java.util.HashSet;
import java.util.Objects;
import java.util.Scanner;
import java.util.Set;

public class MazeSolving {
    static int xLength;
    static int yLength;
    static class CheckModel{
        int x;
        int y;
        public CheckModel(int x,int y){
            this.x = x;
            this.y = y;
        }
        @Override
        public int hashCode(){
            return Objects.hash(x, y);
        }
        @Override
        public boolean equals(Object o){
            if(o==this){
                return true;
            }
            if(o==null||getClass()!=o.getClass()){
                return false;
            }
            CheckModel check = (CheckModel) o;
            return x == check.x && y==check.y;
        }
    }

    //wallSet代表墙壁坐标，checkSet用于存储在搜索路径过程中检查过的坐标，finishSet用于存储已经找到终点的坐标
    private static void findItOut(int x, int y, Set<CheckModel> wallSet, Set<CheckModel> checkSet, Set<CheckModel> finishSet) {
        if(yLength-1==y&&xLength-1==x){
            finishSet.add(new CheckModel(x,y));//检查当前坐标 (x, y) 是否是迷宫的终点
        }
        if(yLength<=y||x>=xLength){
            return;  //越界了
        }
        checkSet.add(new CheckModel(x,y));//否则添加到已检查坐标
        //北方向
        if(!wallSet.contains(new CheckModel(x,y+1))){
            findItOut(x,y+1,wallSet,checkSet,finishSet);
        }else{
            finishSet.add(new CheckModel(x,y));
        }
        //东方向
        if(!wallSet.contains(new CheckModel(x+1,y))){
            findItOut(x+1,y,wallSet,checkSet,finishSet);
        }else{
            finishSet.add(new CheckModel(x,y));
        }
    }
    public static void main(String[] args){
        try {
            Scanner sc = new Scanner(System.in);
            xLength = sc.nextInt();
            yLength = sc.nextInt();
            int size = sc.nextInt();
            int[][] values = new int[size][2];
            for(int i = 0; i < size; i++){
                values[i][0] = sc.nextInt();
                values[i][1] = sc.nextInt();
            }
            int trapCount = 0;
            int invalidCount = 0;
            Set<CheckModel> wallHashSet = new HashSet<>();
            for(int[] wall:values){
                wallHashSet.add(new CheckModel(wall[0],wall[1]));
            }
            Set<CheckModel> checksHashSet = new HashSet<>();
            Set<CheckModel> finshHashSet = new HashSet<>();
            findItOut(0,0,wallHashSet,checksHashSet,finshHashSet);
            invalidCount = xLength*yLength-checksHashSet.size()-wallHashSet.size();
            //整个迷宫中的格子数减去检查过的格子数和包含障碍物的格子数等于无法到达数量

            /*
            * 这里使用 finishHashSet 中的每个坐标作为起点，再次调用 findItOut 进行深度优先搜索。
            * 如果搜索得到的路径中不包含终点 (xLength - 1, yLength - 1)，则说明这条路径是无效的，
            * trapCount 就会增加。这样，trapCount 表示的是无效的路径的数量。
            *
            * */
            for(CheckModel model:finshHashSet){
                Set<CheckModel> checksT = new HashSet<>();
                Set<CheckModel> finishT = new HashSet<>();
                findItOut(model.x, model.y, wallHashSet,checksT,finishT);
                if(!finishT.contains(new CheckModel(xLength-1,yLength-1))){
                    trapCount++;
                }
            }
            System.out.println(trapCount+" "+invalidCount);
        }catch (Exception e){
            e.printStackTrace();
            System.out.println("input error");
        }
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103