//堆代码 www.duidaima.com //我们以红点位置为坐标{0,0},绿色位置坐标为{2,2} //目标的坐标位置 let target = { x: 0, y: 0 }; //绿色起点的坐标位置 let currentLocation = { x: 2, y: 2 }; let used = []; //用来标记地图上哪些点是走过的 let reached = false; //是否能到达目标位置 // 表示灰色区域的格子 const illegalLocation = [ { x: 0, y: 2 }, //序号1的坐标 { x: 0, y: 1 }, //序号4的坐标 { x: 1, y: 1 } //序号5的坐标 ]; function isLegalLocation({ x, y }, illegalLocation) { let flag = true; //位置不能在地图坐标之外 if (x < 0 || x > 2 || y < 0 || y > 2) { return (flag = false); } //不能走的路径 for (const { x: locX, y: locY } of illegalLocation) { if (x === locX && y === locY) { flag = false; } } return flag; } //向左移动 function toLeft({ x, y }) { return { x: x - 1, y }; } //向上移动 function toTop({ x, y }) { return { x, y: y + 1 }; } //向右移动 function toRight({ x, y }) { return { x: x + 1, y }; } //向下移动 function toBottom({ x, y }) { return { x, y: y - 1 }; } function dfs(target, location, illegalLocation, used) { // 如果当前位置与目标坐标相同表示可以抵达 if (Object.entries(target).toString() === Object.entries(location).toString()) { console.log('reached', location); return (reached = true); } let current = location; const newIllegalLocation = illegalLocation.concat(used); //假设按照“左>上>右>下”的顺序走 if (isLegalLocation(toLeft(location), newIllegalLocation)) { current = toLeft(location); } else if (isLegalLocation(toTop(location), newIllegalLocation)) { current = toTop(location); } else if (isLegalLocation(toRight(location), newIllegalLocation)) { current = toRight(location); } else if (isLegalLocation(toBottom(location), newIllegalLocation)) { current = toBottom(location); } else { //走不通了就直接返回 return false } used.push(current); //将刚才走过的格子标记为已走过 return dfs(target, current, illegalLocation, used); //递归下去 } dfs(target, currentLocation, illegalLocation, used);
// 堆代码 www.duidaima.com //我们以红点位置为坐标{0,0},绿色位置坐标为{2,2} //目标的坐标位置 let target = { x: 0, y: 0 }; //绿色起点的坐标位置 let currentLocation = { x: 2, y: 2 }; // 表示灰色区域的格子 const illegalLocation = [ { x: 0, y: 2 }, //序号1的坐标 { x: 0, y: 1 }, //序号4的坐标 { x: 1, y: 1 } //序号5的坐标 ]; function isLegalLocation({ x, y }, illegalLocation) { let flag = true; //位置不能在地图坐标之外 if (x < 0 || x > 2 || y < 0 || y > 2) { return (flag = false); } //不能走的路径 for (const { x: locX, y: locY } of illegalLocation) { if (x === locX && y === locY) { flag = false; } } return flag; } //向左移动 function toLeft({ x, y }) { return { x: x - 1, y }; } //向上移动 function toTop({ x, y }) { return { x, y: y + 1 }; } //向右移动 function toRight({ x, y }) { return { x: x + 1, y }; } //向下移动 function toBottom({ x, y }) { return { x, y: y - 1 }; } function bfs(target, location, illegalLocation) { let reached = false; //是否能到达目标位置 let stack = []; let searched = new Set(); //已经走过的格子 stack.push(location); while (stack.length) { let temp = stack.pop(); const newIllegalLocation = illegalLocation.concat([...searched]); //假设按照“左>上>右>下”的顺序走 if (isLegalLocation(toLeft(temp), newIllegalLocation)) { temp = toLeft(temp); } else if (isLegalLocation(toTop(temp), newIllegalLocation)) { temp = toTop(temp); } else if (isLegalLocation(toRight(temp), newIllegalLocation)) { temp = toRight(temp); } else if (isLegalLocation(toBottom(temp), newIllegalLocation)) { temp = toBottom(temp); } else { //没有通路就直接返回 return false } searched.add(temp); stack.push(temp); for (const { x: locX, y: locY } of searched) { if (target.x === locX && target.y === locY) { //如果当前位置与目标坐标相同表示可以抵达 reached = true; console.log('reached: ', reached); stack = []; break; } } } return reached; } bfs(target, currentLocation, illegalLocation);「广度优先遍历」的思想在生活中随处可见:
2.把一块石头投入平静的水面,激起的一层一层波纹就呈现「广度优先遍历」的特点。