dw网站建设的常用技术,百度开发平台,长春城乡建设部网站首页,电子政务网站建设的实验体会机器人走迷宫
题目 房间有X*Y的方格组成#xff0c;例如下图为6*4的大小。每一个放个以坐标(x,y)描述。 机器人固定从方格(0,0)出发#xff0c;只能向东或者向北前进#xff0c; 出口固定为房间的最东北角#xff0c;如下图的方格(5,3)。 用例保证机器人可以从入口走到出…机器人走迷宫
题目 房间有X*Y的方格组成例如下图为6*4的大小。每一个放个以坐标(x,y)描述。 机器人固定从方格(0,0)出发只能向东或者向北前进 出口固定为房间的最东北角如下图的方格(5,3)。 用例保证机器人可以从入口走到出口。 房间有些方格是墙壁如(4,1),机器人不能经过那儿。 有些地方是一旦到达就无法走到出口的如标记为B的方格称之为陷阱方格。 有些地方是机器人无法达到的如标记为A的方格称之为不可达方格不可达方格不包括墙壁所在的位置 如下实例图中陷阱方格有2个不可达方格有3个。 请为该机器人实现路径规划功能给定房间大小墙壁位置请计算出陷阱方格与不可达方格分别有多少个
输入
第一行为房间的x和y(0 x,y 1000)第二行为房间中墙壁的个数N (0 N X*Y)接着下面会有N行墙壁的坐标 同一行中如果有多个数据以一个空格隔开用例保证所有的输入数据均合法(结尾不带回车换行)
输出
陷阱方格与不可达方格数量两个信息在一行中输出以一个空格隔开。(结尾不带回车换行)
示例一
输入
6 4
5
0 2
1 2
2 2
4 1
5 1输出
2 3示例二
输入
6 4
4
2 0
2 1
3 0
3 1输出
0 4说明
说明不可达方格有4个 (4,0) (4,1) (5,0) (5,1) 解题思路
核心算法是深度优先搜索解决了一道题目判断一个地图中是否有陷阱。代码中有一些细节需要注意。
读取输入
在JavaScript中我们可以使用readline模块。为了避免一次性读取所有输入我们可以通过监听stdin的line事件每读取一行执行一次。
定义Check类
由于JavaScript中没有类的概念我们可以使用一个对象字面量来代替这个类。我们需要实现equals和hashCode方法以便在Set中使用。equals方法检查两个对象是否相等hashCode方法为对象计算
Code
const readline require(readline);class Check {constructor(x, y) {this.x x;this.y y;}equals(other) {return this.x other.x this.y other.y;}hashCode() {return this.x * 31 this.y;}
}let xLen;
let yLen;function main() {const rl readline.createInterface({input: process.stdin,output: process.stdout,});rl.on(line, (line) {const input line.trim().split( ).map(Number);if (xLen undefined) {xLen input[0];yLen input[1];const n input[2];const walls [];for (let i 0; i n; i) {walls.push([parseInt(rl.read()), parseInt(rl.read())]);}solveMethod(walls);}});
}function solveMethod(walls) {let trapCount 0;let invalidCount 0;const wallSet new Set();for (const wall of walls) {wallSet.add(new Check(wall[0], wall[1]));}const checks new Set();const finish new Set();findOut(0, 0, wallSet, checks, finish);invalidCount xLen * yLen - checks.size - wallSet.size;for (const check of finish) {const checksT new Set();const finishT new Set();findOut(check.x, check.y, wallSet, checksT, finishT);if (!finishT.has(new Check(xLen - 1, yLen - 1))) {trapCount;}}console.log(trapCount invalidCount);
}function findOut(x, y, wallSet, checks, finish) {if (x xLen - 1 y yLen - 1) {finish.add(new Check(x, y));}if (x xLen || y yLen) {return;}checks.add(new Check(x, y));if (!wallSet.has(new Check(x, y 1))) {findOut(x, y 1, wallSet, checks, finish);} else {finish.add(new Check(x, y));}if (!wallSet.has(new Check(x 1, y))) {findOut(x 1, y, wallSet, checks, finish);} else {finish.add(new Check(x, y));}
}
版权说明
试题来源华为 OD 联盟整理收集
题解解题思路 与 代码 为原创内容该部分版权由 OD 联盟共同拥有并授权组内成员发布。
目标 助你解开所有机试题
