我想编写一个函数来打印所有可能的模式,如下例所示。在任何情况下,我们都必须从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,然后随机化2d数组中的其余数字,直到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++;
    }
}

最佳答案

在这里,您使用3x3矩阵跟踪状态(访问的节点和存储所走的路径),x/y坐标表示当前位置,并生成四个递归调用来处理可能的移动方向(带边界检查)。
但是,我不确定运行到9的循环是否有效——这将在每帧产生36个递归调用。这在某些实现中可能是可行的,但我认为最简单的方法是将每个帧视为在给定x/y坐标对的情况下探索一个可能的方向,然后在从该正方形递归地探索所有方向后回溯(撤消移动)。每当我们进入最后一步,我们就知道我们已经探索了所有的正方形,现在是打印当前解决方案路径的时候了。
这是实现这一点的代码,基本上是对尺寸进行硬编码。一个练习是将代码泛化为任意大小的矩阵,并返回将打印与遍历逻辑分离的路径。我还选择将state移出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) {
    int 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

07-24 09:46
查看更多