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

我想写一个函数，像下面的例子一样打印所有可能的模式。在任何情况下，我们都必须从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坐标对的情况下探索一个可能的方向，然后在从该正方形递归探索所有方向后回溯(取消移动(。每当我们进入最后一步时，我们就知道我们已经探索了所有的正方形，是时候打印当前的解决方案路径了。

这是实现这一点的代码，基本上是对尺寸进行硬编码。一个练习是将代码概括为任何大小的矩阵，并返回将打印与遍历逻辑分离的路径。我还选择将状态从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;
}

输出：

相关内容

最新更新

热门标签：