poj3009
原题链接：http://poj.org/problem?id=3009
这道题目中文的描述大概是有一冰球，可以前后左右击打它，不能出边、不能一开始就碰壁、不能斜着走，极大后除非遇到边才能停下来，停下来后墙壁裂开(这个地方应该是为了防止重复运动)，直到遇到终点，终点是一个摩擦力巨大的位置，所以只要行进轨道中存在该终点则游戏结束，不可高于十次击打。求最少的到达终点的击打次数。
部分配图如下，这是题目给出的例图，S为起点，G为终点
这里讲一下我们的思路
寻找最小的路径来通往终点，首先我们定义一个地图，0为空地、1为墙壁、2为起点、3为终点，在算法开始前，先将该起点位置保存，并将该位置置为空地，getStartFlag和getEndFlag用于提前结束寻找起点与终点循环，函数isLegal用于判断现在的情况下的棋子位置是否合法。深度优先遍历的逻辑如下：结束判断为：如果现在的起点位置正好是终点位置，那么说明现在正好是找到了最终点，那么退出；而如果此时的步数answerStep大于十或大于另设的最大阈值了，那么也退出。每次对下一步进行循环的时候，都要做一件事情=>对四个方向进行遍历，所以这里我们用一个向量数组表示我们位移的方向。那么对单一方向进行位移的过程中，我们用now对象来储存当前的位置，一直循环直到碰壁或接触到终点，碰壁则退出循环，终点则结束。退出循环后当然还要进行一次判断，判断该次位移是否只“移动了一位”，这里判断只移动了一位的原因是，在题目中不能往紧贴墙的位置击打，同时我们由于碰壁退出循环的条件是当前的map[now.x][now.y] == 1，所以若只位移了一次，说明这次的位移是“撞碎紧贴墙壁”造成的位移，所以如果是这样的话，我们就要进行下一个方向的位移阶段了。那么若是不是“撞碎紧贴墙壁”造成的位移，那么这次位移我们可以认为是OK的，我们将这里的map置为0，让start位移到这里，并减去一个单位的d向量（因为其实我们现在是在碎墙上），继续下一次的查找。每次函数退出，会将刚才的地图置为1，步数减一，视为悔步。
所以我们的代码如下，使用的是JS的语法，但是用其他语言也是OK的，没有什么需要特别注意的地方，大家如果有什么不懂的地方可以在评论区询问我哦
// poj3009 let map = [ [1, 0, 0, 2, 1, 0], [1, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 3], [0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 1], [0, 1, 1, 1, 1, 1], ]; let width = 6; let height = 6; //起始 let start = {}; //目标 let end = {}; // 简化调试步骤 let getStartFlag = false; let getEndFlag = false; // 移动的向量 let d = [[-1, 0], [1, 0], [0, -1], [0, 1]]; let result = 11; for (let i = 0; i < height; i++) { for (let j = 0; j < width; j++) { if (getStartFlag && getEndFlag) { break; } if (map[i][j] == 2) { start.x = i; start.y = j; map[i][j] = 0; getStartFlag = true } if (map[i][j] == 3) { end.x = i; end.y = j; getEndFlag = true } } } dfs(start, 0); console.log(`${result == 11 ? '-1' : result}`); function dfs(start, answerStep) { // 该函数判断该now位置是否合法 let isLegal = now => (0 <= now.x && 0 <= now.y && now.x < height && now.y < width); // 结束判断 if (start.x == end.x && start.y == end.y) { if (result > answerStep) { result = answerStep; } return; } // 结束判断 if (answerStep == 10 || answerStep >= result) { return; } // 对四个方向进行循环 for (let i = 0; i < 4; i++) { let now = {} now.x = start.x + d[i][0]; now.y = start.y + d[i][1]; // 对单一方向的深入 while (isLegal(now) && map[now.x][now.y] != 1) { if (now.x == end.x && now.y == end.y) { answerStep++; if (result > answerStep) { result = answerStep; } return; } now.x += d[i][0]; now.y += d[i][1]; } // 起步就撞石头了 => 判断在该方向上是否只位移了一段 if ((now.x == start.x + d[i][0] && now.y == start.y + d[i][1]) || !isLegal(now)) { continue; } // 石头现在已经在“墙上”了，所以这里要将这个墙打碎，并让石头后退一格 map[now.x][now.y] = 0; let temp = {}; temp.x = now.x - d[i][0]; temp.y = now.y - d[i][1]; dfs({ x: temp.x, y: temp.y }, ++answerStep); answerStep--; map[now.x][now.y] = 1; } }