几天前做了一题相对复杂的算法题，算是路径题。一般此类题目能想到的解法有 DFS、BFS、动态规划、贪心、迪杰斯特拉算法（不适用）、弗洛伊德算法（不适用）等。
接下来看下完整的题目，题目很长，当时读题（全英文）就花了近半小时。为了方便理解，我将其描述为容易理解的语言。
上图是一个 m * n 的矩阵，S 为出发的起点（永远为左下角），A 为所要达到的终点。可以从任一方向前进（上下左右），但是水平前进时，需要有路，即必须有短横才能同行；而纵向的同行可以直接跳跃到下一个短横。
需要求解的是，纵向路径长版的最小值。即上图中的答案为 2。该图的其他路径，例如从 S 先向上到 6 的第一个板，之后再向右到达 A。但是这样使得纵向路径的长板为 5，没有达到最优的 2。
这个图只是一个个例，要注意的是，其路径不一定都是向右和向上，有可能先向上后向下也会是最优解。
首先，我想到了 DFS 求解，即可就开始写。定义一个 GraphDFS，将一些属性设置好，arr 为这个图，mark 是记忆恢复使用的数组，ans 为最优解，curMax 用于记录一个路径中的长版。
Jeffrey的博客
public class GraphDFS {
private final int[][] arr;
private final int[][] mark;
private final int m;
private final int n;
private int ans;
private int curMax;
// start -> (m - 1, 0)
// end -> arr[i][j] = 2
public GraphDFS(int[][] arr) {
this.m = arr.length;
this.n = arr[0].length;
this.arr = arr;
this.mark = new int[m][n];
this.ans = m;
this.curMax = 1;
}
}
边界判断，这个很常见，不赘述。
private boolean inArea(int i, int j) {
return i >= 0 && j >= 0 && i < m && j < n;
}
之后是 DFS 的核心算法，首先判断是否越界，之后到达 S 点的判断（之前没有提到，S 点的数组值为 2，短横的值为 1，其他为 0）。之后是从四个方向分别搜索，这里传了一个布尔值，这是由于纵向遍历时，需要计算当前的长版，所以在自定义的 ops 方法内会有些不同。
private void dfs(int i, int j) {
if (!inArea(i, j)) {
return;
}
if (arr[i][j] == 2) {
ans = Math.min(ans, curMax);
return;
}
ops(up(i, j), i, true);
ops(down(i, j), i, true);
ops(left(i, j), i, false);
ops(right(i, j), i, false);
}
四个方向的搜索以获得，最新的位置，这里复杂的地方是 up 和 down 方法的搜索，需要向上或向下找到一个板，这里需要用到 while，但没有办法，这部分时间复杂度只能贡献。
private int[] up(int i, int j) {
while (inArea(--i, j)) {
if (arr[i][j] == 1 || arr[i][j] == 2) {
return new int[]{i, j};
}
}
return new int[]{-1, -1};
}
private int[] down(int i, int j) {
while (inArea(++i, j)) {
if (arr[i][j] == 1 || arr[i][j] == 2) {
return new int[]{i, j};
}
}
return new int[]{-1, -1};
}
private int[] left(int i, int j) {
if (!inArea(i, j - 1) || (arr[i][j - 1] != 1 && arr[i][j - 1] != 2)) {
return new int[]{-1, -1};
}
return new int[]{i, j - 1};
}
private int[] right(int i, int j) {
if (!inArea(i, j + 1) || (arr[i][j + 1] != 1 && arr[i][j + 1] != 2)) {
return new int[]{-1, -1};
}
return new int[]{i, j + 1};
}
ops 是我自定义方法，抽取了 DFS 操作方向的公用代码，也可以直接写在 DFS 里，会比较长。纵向时需要更新 curMax 长板值。
private void ops(int[] dir, int i, boolean cmp) {
int x = dir[0];
int y = dir[1];
int tmpCurMax = curMax;
if (x != -1 && mark[x][y] != 1) {
if (cmp) {
curMax = Math.max(curMax, Math.abs(i - x));
}
mark[x][y] = 1;
dfs(x, y);
mark[x][y] = 0;
if (cmp) {
curMax = tmpCurMax;
}
}
}
代码到这里其实基本结束了，用主方法测一下，能得到正确值。
public static void main(String[] args) {
int[][] arr = new int[][]{
{1, 1, 0, 0, 1, 1},
{0, 0, 1, 1, 0, 0},
{1, 1, 1, 1, 1, 2},
{0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 1, 1},
{0, 0, 0, 1, 1, 0},
{1, 1, 1, 1, 1, 1}
};
GraphDFS graph = new GraphDFS(arr);
System.out.println(graph.getAns());
}
但这个问题到这里远没有结束，这里用 DFS 搜索确实可以求解这个矩阵图，其原因是矩阵很小，但是题目给到了一个 50 * 50 的矩阵，用上述代码剪枝后仍然无法求解，复杂度过高，后续有时间会再写一个 BFS 的版本，可以降低一些复杂度，或许可以求解大矩阵。