廊坊网站制作公司排名,常用网站开发模式,为网站添加isapi扩展,网站制作平台建设题目
1.房间有XY的方格组成#xff0c;例如下图为64的大小。每一个方格以坐标(x,y) 描述。 2.机器人固定从方格(0, 0)出发#xff0c;只能向东或者向北前进#xff0c;出口固定为房间的最东北角#xff0c;如下图的 方格(5,3)。用例保证机器人可以从入口走到出口。 3.房间…题目
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;}Overridepublic int hashCode(){return Objects.hash(x, y);}Overridepublic boolean equals(Object o){if(othis){return true;}if(onull||getClass()!o.getClass()){return false;}CheckModel check (CheckModel) o;return x check.x ycheck.y;}}//wallSet代表墙壁坐标checkSet用于存储在搜索路径过程中检查过的坐标finishSet用于存储已经找到终点的坐标private static void findItOut(int x, int y, SetCheckModel wallSet, SetCheckModel checkSet, SetCheckModel finishSet) {if(yLength-1yxLength-1x){finishSet.add(new CheckModel(x,y));//检查当前坐标 (x, y) 是否是迷宫的终点}if(yLengthy||xxLength){return; //越界了}checkSet.add(new CheckModel(x,y));//否则添加到已检查坐标//北方向if(!wallSet.contains(new CheckModel(x,y1))){findItOut(x,y1,wallSet,checkSet,finishSet);}else{finishSet.add(new CheckModel(x,y));}//东方向if(!wallSet.contains(new CheckModel(x1,y))){findItOut(x1,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;SetCheckModel wallHashSet new HashSet();for(int[] wall:values){wallHashSet.add(new CheckModel(wall[0],wall[1]));}SetCheckModel checksHashSet new HashSet();SetCheckModel 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){SetCheckModel checksT new HashSet();SetCheckModel 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);}}}
