广度优先搜索
可用于： 查找是否可以从 A 到 B 2.从 A 到 B 最少走几步
实现思路：
- 将图的内容存在散列表中，针对一个节点（入口），可以得到它的所有邻居节点（出口）
- 将第一层节点推入队列，弹出第一个进行循环判断，在队列不为 0 的条件下始终执行循环
- 循环中判断当前节点是否为目标节点，如果不是记录已判断过，如果是则结束。
广度优先搜索使用-钟馗抓鬼
题目：
追赶妖怪
Description
一身正气的钟馗四处降妖，一天他发现一只狐妖正在祸害百姓，他连忙追赶上去准备除妖，可是狐妖很聪明，她自知敌不过钟馗，便逃入山林，企图消耗钟馗的体力。钟馗在树林里面可以自由移动，而且他有一个法术：可以从当前坐标(x,y)直接移动到(2x,2y)的位置。钟馗为了不枉送性命，找到人称"人间诸葛亮"的你，希望你能帮他判断他能否在体力未耗尽到达狐妖的藏匿地点（如果到达狐妖藏身之处还剩余0点体力也是可以的）。
注意：钟馗一开始拥有n点体力，每次普通移动或者使用法术移动会消耗1点体力值，当体力消耗完毕(n<=0)便无法再进行移动。
现在给钟馗移动方式一个规定：
a.如果钟馗不使用法术，他可以从(x,y)移动到(x-1,y),(x+1,y),(x,y-1),(x,y+1)中的任意一个位置.
b.如果钟馗使用法术，他可以从当前坐标(x,y)直接移动到(2x,2y)的位置.
Input
输入包含3行。
第一行包含一个数字n，表示钟馗的初始体力值。1<n<=500
第二行两个整数表示钟馗初始坐标。
第三行两个整数表示狐妖藏匿坐标。
注意：狐妖不会移动。树林可以看做一个矩形，四个角的坐标分别为(0,0),(0,500),(500,0),(500,500)。钟馗移动的位置不能超出树林的范围。
Output
输出只有一行。
如果钟馗能够到达狐妖藏匿位置输出"YES",如果钟馗无法到达狐妖藏匿位置输出"NO"
Sample Input
50
4 4
9 9
5
0 0
0 5
1
0 0
1 0
1
0 0
2 2
1
0 0
500 500
Sample Output
YES
YES
YES
NO
NO
解法：
function canGetLoc(n, zLoc, hLoc) {
const [ zX, zY ] = zLoc; // 钟馗初始坐标
const [ hX, hY ] = hLoc; // 狐妖坐标
let queue = []; // 模拟队列
const travePath = []; // 已经过的路，标记
let canCatch = false;
let step = 1;
// 模拟散列表的一个散列函数
function getMap(x, y, z) {
const r = [];
const newZ = z + 1;
if(x + 1 <= 500) {
r.push([x + 1, y, newZ]);
}
if(x -1 >= 0) {
r.push([x - 1, y, newZ]);
}
if(y+1 <= 500){
r.push([x, y+1, newZ])
}
if(y-1 >= 0) {
r.push([x, y-1, newZ]);
}
if(2*x <= 500 && 2*y <= 500) {
r.push([2*x, 2*y, newZ]);
}
return r;
}
queue = queue.concat(getMap(zX, zY, 0));
while (queue.length > 0) {
// 只要不达到目标就一直走
// 弹出
const target = queue.shift();
const [ tX, tY, tZ ] = target;
const flag = `${tX}_${tY}`;
if(tZ > n) {
// 已无法捕获
break;
}
if(travePath.includes(flag)) {
// 之前已经经过了一次
continue;
}
travePath.push(flag);
if(hX === tX && hY === tY) {
// 抓到了
step = tZ;
canCatch = true;
break;
} else if(tX > 500 || tY > 500 || tX < 0 || tY < 0) {
// 超出范围了
continue;
} else {
// 没超出范围也没抓到，就把当前节点的邻居再压入队列
queue = queue.concat(getMap(tX, tY, tZ));
}
}
console.log('停了', canCatch, n, step);
return canCatch && step <= n ? 'YES' : 'NO';
}
