二维网格问题的解法

经常有面试问题是二维网格问题,比如迷宫问题、迷宫最短路径问题、N皇后问题等等。求解时主要有以下要素:

  • 遍历:对每个格子(位置)进行遍历。
  • 搜索相邻的格子。

总体的搜索可以有深度优先(DFS)和广度优先(BFS)之分。

根据我自己的经验,在有限的时间内解答这类问题时,要注意以下几点:

二维数组的行列顺序

二维数组是按照先行后列的顺序存储的:

void func(int[][] data) {
    if (data == null || data.length = 0 || data[0].length == 0) {
        // ...
        return;
    }

    int rows = data.length;
    int cols = data[0].length;

    for (int r = 0; i < rows; ++r) {
        // 或者更好的写法是:c < data[r].length
        // 但这类问题一般都是个矩形区域,因此把cols提前定好,代码更简洁
        for (int c = 0; c < cols; ++c) {
            data[r][c] = 0;
        }
    }

    // ...
}

循环变量名称

循环变量名称似乎根本不是个问题,一般会用i和j来表示。但在有限时间而且缺乏IDE帮助debug的情况下,对于二维格子问题,很容易引起思维混乱。我自己就有一次在线测试时,因为把行和列弄颠倒了,导致时间到了还无法把程序调通。后来自己“复盘”的时候,才发现原因所在。

因此,建议把变量名称弄得一看就懂:

  • 行数和列数:rows,cols
  • 表示行和列的循环变量名:r,c

例如:

for (int r = 0; r < rows; ++r) {
    for (int c = 0; c < cols; ++c) {
        data[r][c] = 0;
    }
}

搜索相邻的格子

一般我会按东西南北四个方向编写:

// N
if (r > 0) {
    backtrack(r - 1, c);
}

// S
if (r < rows - 1) {
    backtrack(r + 1, c);
}

// W
if (c > 0) {
    backtrack(r, c - 1);
}

// E
if (c < cols - 1) {
    backtrack(r, c + 1);
}

这样看似很有效率,但很啰嗦,而且在情急之下容易犯错。我经常会因为拷贝粘贴的代码中没改完全而导致程序不能通过,而之后要用肉眼去观察一遍来找出错误的话,很费时间。因此,在效率没有多少区别的情况下,程序越简短越好。

//                                        N   S   W   E
private static final int[] rowOffsets = {-1,  1,  0,  0};
private static final int[] colOffsets = { 0,  0, -1,  1};

private void backtrack(int[][] data, int[][] visited, int r, int c) {
    // ...

    int rows = data.length;
    int cols = data[0].length;
    BiPredicate<Integer, Integer> isValid = (row, col) ->
            row >= 0 && row < rows && col >= 0 && col < cols;

    // 尝试搜索相邻的格子
    for (int i = 0; i < rowOffsets.length; ++i) {
        int r1 = r + rowOffset[i];
        int c1 = c + colOffset[i];

        if (isValid.test(r1, c1) && !visited[r1][c1]) {
            backtrack(data, visited, r1, c1);
        }
    }

    // ...
}

有人喜欢在枚举相邻格子时,按东南西北的顺序转一圈。在我看来似乎没什么必要。最重要的是简单且不易弄错,所以我都是选择按北、南、东、西的顺序轮转。当然,每个人习惯不同,可以选择自己最舒适的顺序。

总结:对于编程来说,最好是从一开始就不要把bug放进去,否则要找出来就需要花费成倍的时间。因此,要选择各种一看就懂的方式写代码,防止写到中间自己都迷糊了。另外,为了避免查找bug的时间过长,应该尽量写简短的代码(当然不是那种为了短而短的十分缺乏可读性的那种)。

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注