JavaScript遍历实现DFS算法和BFS算法

//我们以红点位置为坐标{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);

//我们以红点位置为坐标{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);