廣度優(yōu)先搜索
可用于： 查找是否可以從 A 到 B 2.從 A 到 B 最少走幾步
實現(xiàn)思路：
- 將圖的內(nèi)容存在散列表中，針對一個節(jié)點（入口）轩勘，可以得到它的所有鄰居節(jié)點（出口）
- 將第一層節(jié)點推入隊列朽肥，彈出第一個進(jìn)行循環(huán)判斷叛氨，在隊列不為 0 的條件下始終執(zhí)行循環(huán)
- 循環(huán)中判斷當(dāng)前節(jié)點是否為目標(biāo)節(jié)點瘪吏，如果不是記錄已判斷過铃彰，如果是則結(jié)束。
廣度優(yōu)先搜索使用-鐘馗抓鬼
題目：
追趕妖怪
Description
一身正氣的鐘馗四處降妖歇式，一天他發(fā)現(xiàn)一只狐妖正在禍害百姓驶悟，他連忙追趕上去準(zhǔn)備除妖，可是狐妖很聰明贬丛，她自知敵不過鐘馗撩银，便逃入山林给涕，企圖消耗鐘馗的體力豺憔。鐘馗在樹林里面可以自由移動，而且他有一個法術(shù)：可以從當(dāng)前坐標(biāo)(x,y)直接移動到(2x,2y)的位置够庙。鐘馗為了不枉送性命恭应，找到人稱"人間諸葛亮"的你，希望你能幫他判斷他能否在體力未耗盡到達(dá)狐妖的藏匿地點（如果到達(dá)狐妖藏身之處還剩余0點體力也是可以的）耘眨。
注意：鐘馗一開始擁有n點體力昼榛，每次普通移動或者使用法術(shù)移動會消耗1點體力值，當(dāng)體力消耗完畢(n<=0)便無法再進(jìn)行移動剔难。
現(xiàn)在給鐘馗移動方式一個規(guī)定：
a.如果鐘馗不使用法術(shù)胆屿，他可以從(x,y)移動到(x-1,y),(x+1,y),(x,y-1),(x,y+1)中的任意一個位置.
b.如果鐘馗使用法術(shù)，他可以從當(dāng)前坐標(biāo)(x,y)直接移動到(2x,2y)的位置.
Input
輸入包含3行偶宫。
第一行包含一個數(shù)字n非迹，表示鐘馗的初始體力值。1<n<=500
第二行兩個整數(shù)表示鐘馗初始坐標(biāo)纯趋。
第三行兩個整數(shù)表示狐妖藏匿坐標(biāo)憎兽。
注意：狐妖不會移動。樹林可以看做一個矩形吵冒，四個角的坐標(biāo)分別為(0,0),(0,500),(500,0),(500,500)纯命。鐘馗移動的位置不能超出樹林的范圍。
Output
輸出只有一行痹栖。
如果鐘馗能夠到達(dá)狐妖藏匿位置輸出"YES",如果鐘馗無法到達(dá)狐妖藏匿位置輸出"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; // 鐘馗初始坐標(biāo)
const [ hX, hY ] = hLoc; // 狐妖坐標(biāo)
let queue = []; // 模擬隊列
const travePath = []; // 已經(jīng)過的路亿汞，標(biāo)記
let canCatch = false;
let step = 1;
// 模擬散列表的一個散列函數(shù)
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) {
// 只要不達(dá)到目標(biāo)就一直走
// 彈出
const target = queue.shift();
const [ tX, tY, tZ ] = target;
const flag = `${tX}_${tY}`;
if(tZ > n) {
// 已無法捕獲
break;
}
if(travePath.includes(flag)) {
// 之前已經(jīng)經(jīng)過了一次
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 {
// 沒超出范圍也沒抓到，就把當(dāng)前節(jié)點的鄰居再壓入隊列
queue = queue.concat(getMap(tX, tY, tZ));
}
}
console.log('停了', canCatch, n, step);
return canCatch && step <= n ? 'YES' : 'NO';
}
