我想编写一个函数来打印所有可能的模式,如下例所示。在任何情况下,我们都必须从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