c - 用C打印二维手机键盘中的每个解锁图案

Question

我想编写一个函数来打印所有可能的模式，如下例所示。在任何情况下，我们都必须从 3x3 数组的左上角开始。与解锁手机的图案类似，只不过线不能对角线走，必须穿过每个盒子。

1--->2--->3           1--->2--->3
          |                     |
          v                     v
8<---7    4     or    6<---5<---4
|    ^    |           |
v    |    v           v
9    6<---5           7--->8--->9

我首先编写一段代码，其中 [0][0] 被分配为 1，然后随机化二维数组中的其余数字，直到 1[0] 或0 等于 2，依此类推。但我觉得这让问题变得更加难以解决。

然后尝试使用递归一次又一次调用makePattern函数，直到数组发生改变；但是，由于以下代码行，它将数组中的所有值更改为 2:

int value = 2;    
array[x][y] = value;

但是，我不知道如何循环这个值，以便它随着函数再次调用而增加。

#include <stdio.h> 
#include <stdlib.h>

#define ROW 3
#define COLUMN 3

int makePattern(int array[ROW][COLUMN], int x, int y);

int main(void) {
    int x, y;
    int count = 2;
    int i, j;

    int array[ROW][COLUMN] = {
        {'1', '0', '0'},
        {'0', '0', '0'},
        {'0', '0', '0'},
    };

    makePattern(array, 0, 0);

    for (i = 0; i < ROW; i++) {
        for (j = 0; j < COLUMN; j++) {
            printf("%d", array[i][j]);
        }

        printf("\n");
    }

    return 0;
}

int makePattern(int array[ROW][COLUMN], int x, int y) {
    int value = 2;
    array[x][y] = value;

    for (value = 2; value < 9; value++) {
        if (x + 1 < ROW && array[x+1][y] == '0') {
            makePattern(array, x + 1, y);
        }

        if (x - 1 >= 0 && array[x - 1][y] == '0') {
            makePattern(array, x - 1, y);
        }

        if (y + 1 < COLUMN && array[x][y + 1] == '0') {
            makePattern(array, x, y + 1);
        }

        if (y - 1 >= 0 && array[x][y - 1] == '0') {
            makePattern(array, x, y - 1);
        }

        value++;
    }
}

Answer 1

您走在正确的轨道上，因为您使用 3x3 矩阵来跟踪状态(访问的节点并存储所采取的路径)，x/y 坐标来表示当前位置并生成四个递归调用处理可能的移动方向(带有边界检查)。

但是，我不确定运行到 9 的循环是否会起作用——这将在每帧产生 36 次递归调用。这在某些实现中可能可行，但我认为最简单的方法是将每一帧视为探索给定 x/y 坐标对的一个可能方向，然后在从该正方形递归探索所有方向后回溯(撤消移动)。每当我们到达最后一步时，我们就知道我们已经探索了所有的方 block ，是时候打印当前的解决方案路径了。

这是实现此目的的代码，并且基本上对尺寸进行了硬编码。一个练习是将代码推广到任意大小的矩阵，并返回将打印与遍历逻辑分开的路径。我还选择将状态移出 main 函数。

#include <stdbool.h>
#include <stdio.h>
#include <string.h>

static void print_unlock_patterns_r(int pad[3][3], int x, int y, int step) {
    static int const directions[][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    pad[y][x] = 1 + step;

    for (int i = 0; i < 4; i++) {
        int xp = x + directions[i][0];
        int yp = y + directions[i][1];

        if (xp >= 0 && xp < 3 && yp >= 0 && yp < 3 && !pad[yp][xp]) {
            print_unlock_patterns_r(pad, xp, yp, step + 1);
        }
    }

    if (step == 8) {
        for (int i = 0; i < 3; i++, puts("")) {
            for (int j = 0; j < 3; printf("%d", pad[i][j++]));
        }

        puts("");
    }    

    pad[y][x] = 0;
}

void print_unlock_patterns() {
    int pad[3][3];
    memset(pad, 0, sizeof(pad));
    print_unlock_patterns_r(pad, 0, 0, 0);
}

int main(void) {
    print_unlock_patterns();
    return 0;
}

输出:

123
894
765

123
874
965

123
654
789

129
438
567

145
236
987

189
276
345

187
296
345

167
258
349