算法题解:拯救007 by javascript

题目描述:给定一张地图，007开始位于中间的河流中央,如图所示

地图.png

007在鳄鱼堆里想要活命，他想要活命的的方法有很多，不过这里他选择跳到鳄鱼头上,注意007的跳跃能力是有限的，他只能跳到跳跃能力所及的鳄鱼头上,如果最终能跳出地图边界，代表上岸，则007活命，反之可怜007不能活命。

跳跃能力图解,如图,当前007只能跳到圆域范围内的那一个节点.png

更科学的描述是：给定一张地图,地图上存在许多节点,从（0,0）开始，节点间是否存在边关系的依据是,节点间的距离是否小于某一最大值（这里设定为detectDistance）。依此关系建图，然后搜索是否存在一条路径，路径的最后一个节点距离地图边界小于detectDistance，如果小于则输出该路径，如果不存在任何一条这样的路径，则什么都不输出。

先上源代码,然后再一一详解

class node {
  constructor(data, x, y) {
    this.detect = false;
    this.data = data;
    this.edge = [];
    this.site = [x, y]
  }
  dfs(roadStores) {

    this.detect = true;
    roadStores.push({
        data: this.data,
        site : this.site
      }
    ); //记录当前路径
    if (node.isSafe(this.site[0], this.site[1])) {
      console.log([...roadStores]);
      roadStores.pop();
      return;
    }
    for (const node of this.edge) { //对当前节点的边一个一个尝试
      if (node.detect == false) {
        this.dfs.call(node, roadStores);
      }
    }
  }
  static detectDistance = 8.1
  static countEdge(nodeStores) {
    for (const node of nodeStores) {
      for (const otherNode of nodeStores) {
        if (otherNode == node) {
          continue;
        }
        let δx = node.site[0] - otherNode.site[0];
        let δy = node.site[1] - otherNode.site[1];
        δx = Math.abs(δx);
        δy = Math.abs(δy);
        if (Math.sqrt(δx * δx + δy * δy) <= this.detectDistance) {
          node.edge.push(otherNode);
        }
      }
    }
  }
  static isSafe(x, y) {
    return Math.abs(20 - x) < node.detectDistance || Math.abs(20 - y) < node.detectDistance
  }
  
}
//假设地图是40*40的小地图
let nodeStores = [
  new node(0, 0, 0),
  new node(1, 5, 5),
  new node(2, 10, 10),
  new node(3, 15, 15),
  new node(4, 15, 10),
  new node(5, 12, 10),
]
node.countEdge(nodeStores); //建边
let roadStores = [];
nodeStores[0].dfs(roadStores)

节点内部:

class node {
  constructor(data, x, y) {
    this.detect = false;//是否被探测
    this.data = data; //节点所占有的信息
    this.edge = []; //当前节点和别的节点的边关系
    this.site = [x, y] //当前节点的位置
  }

第一步:建图

let nodeStores = [
  new node(0, 0, 0),
  new node(1, 5, 5),
  new node(2, 10, 10),
  new node(3, 15, 15),
  new node(4, 15, 10),
]

这个没什么好解释的,为了方便读者，我这里特地画一张图出来。如下图

image.png

第二步:建边,主要就是

node.countEdge(nodeStores); //建边
static detectDistance = 8.1 //007的跳跃距离是8
static countEdge(nodeStores) {
    for (const node of nodeStores) {
      for (const otherNode of nodeStores) {
        if (otherNode == node) {
          continue;
        }
        let δx = node.site[0] - otherNode.site[0];
        let δy = node.site[1] - otherNode.site[1];
        δx = Math.abs(δx);
        δy = Math.abs(δy);
        if (Math.sqrt(δx * δx + δy * δy) <= this.detectDistance) {
          node.edge.push(otherNode);
        }
      }}
  }

这里注意探测距离8.1是因为有时候计算精度问题,JavaScript里有时候0.211-0.111===0.1是错误的，特地增加了0.1的容错度
且，因为是检测圆的距离来建边，所以这里主要使用的是两点间的距离公式。
建好后如图

image.png

最后一步，dfs检测

let roadStores = [];
nodeStores[0].dfs(roadStores)
dfs(roadStores) {
    this.detect = true;
    roadStores.push({
        data: this.data,
        site : this.site
      }
    ); //记录当前路径
    if (node.isSafe(this.site[0], this.site[1])) { 
      console.log([...roadStores]);
      roadStores.pop();
      return;
    }
    for (const node of this.edge) { //对当前节点的边一个一个尝试
      if (node.detect == false) {
        this.dfs.call(node, roadStores);
      }
    }
  }
 static isSafe(x, y) {//检测是否可跳到岸上
    return Math.abs(20 - x) < node.detectDistance || Math.abs(20 - y) < node.detectDistance
  }
···