基本上，我试图获取一个已经存在的 50 x 50 二维数字数组，并使用代码中给出的原点(iy 和 ix)，用于查找具有相同值和的连接单元格将所有非连接单元替换为 0。一个例子是数组，例如
1 5 3 2 5 5 5
0 1 9 4 5 0 0
3 3 4 5 5 5 5
使用 (1,4) 处的单元格，我会得到一个数组
0 0 0 0 5 5 5
0 0 0 0 5 0 0
0 0 0 5 5 5 5
我当前的代码只是查找所有具有相同高度的单元格，它不会执行任何操作来查找连接的单元格。它本身并没有清理干净。我认为问题在于我如何在 for 循环中遍历列表来检查连接的单元格，但我无法说出问题是什么
我正在使用 C 进行编码。任何帮助将不胜感激!
//Get the "height" of the "origin" cell
int height = array[x][y];
//I copy the original array into the new array,
//but I only copy the cells with values equal to the "height" of the first cell
for (int i = 0; i <= 50; i++)
{
for (int j = 0; j <= 50; j++)
{
if (array[i][j] == height)
{
newarray[i][j] = array[i][j];
}
else
{
newarray[i][j] = 0;
}
}
}
// Iterate through the array, starting from the origin cell.
//If the cell above or to the left isn't connected to it, then turns it into a 0 cell
for (int i = x; i <= 50; i++)
{
for (int j = y; j <= 50; j++)
{
if (newarray[i][j] == height)
{
if (newarray[i][j-1] == height || newarray[i-1][j] == height)
{
newarray[i][j] = height;
}
else
{
newarray[i][j] = 0;
}
}
}
}
//Does the same, but does it towards the origin (0,0). If the cell to the right
//or below isnt connected to it then it turns it into a 0 cell
for (int i = x; i >= 0; i--)
{
for (int j = y; j >= 0; j--)
{
if (array[i][j] == height)
{
if (newarray[i][j+1] == height || newarray[i+1][j] == height)
{
newarray[i][j] = height;
}
else
{
newarray[i][j] = 0;
}
}
}
}
}
编辑:
我也有一个潜在的递归解决方案来解决这个问题，但是当我尝试运行它时出现段错误
void connectedvals(char array[50][50], char newarray[50][50], int x, int y)
{
int height = array[x][y];
newarray[x][y] = array[x][y];
int up = y + 1;
int down = y - 1;
int left = x - 1;
int right = x + 1;
if (up < 50)
{
if (array[x][up] == height)
{
newarray[x][up] = height;
up++;
connectedvals(array, newarray, x, up)
}
}
if (down >= 0)
{
if (array[x][down] == height)
{
newarray[x][down] = height;
down--;
connectedvals(array, newarray, x, down)
}
}
if (right < 50)
{
if (array[right][y] == height)
{
newarray[right][y] = height;
right++;
connectedvals(array, newarray, right, y)
}
}
if (left >= 0)
{
if (array[left][y] == height)
{
newarray[left][y] = height;
left--;
connectedvals(array, newarray, left, y)
}
}
}
最佳答案
递归解决方案存在许多问题，包括:
- 您不会将搜索值传递给递归函数，因此不同的递归调用最终可能会查找不同的值。
- 您不会检查是否已经访问过给定单元格，因此递归不会停止。
以下是不会崩溃的两个版本的代码。
conn29.c — 最低限度修复
此代码修复了第 2 点，结果演示了第 1 点。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
enum { SIZE = 13 };
static
void connectedvals(char array[SIZE][SIZE], char newarray[SIZE][SIZE], int x, int y)
{
if (newarray[x][y] != 0)
return;
int height = array[x][y];
newarray[x][y] = array[x][y];
int up = y + 1;
int down = y - 1;
int left = x - 1;
int right = x + 1;
if (up < SIZE)
{
if (array[x][up] == height)
{
newarray[x][up] = height;
up++;
connectedvals(array, newarray, x, up);
}
}
if (down >= 0)
{
if (array[x][down] == height)
{
newarray[x][down] = height;
down--;
connectedvals(array, newarray, x, down);
}
}
if (right < SIZE)
{
if (array[right][y] == height)
{
newarray[right][y] = height;
right++;
connectedvals(array, newarray, right, y);
}
}
if (left >= 0)
{
if (array[left][y] == height)
{
newarray[left][y] = height;
left--;
connectedvals(array, newarray, left, y);
}
}
}
static void dump_array(const char *tag, int rows, int cols, char array[rows][cols])
{
printf("%s (%dx%d):\n", tag, rows, cols);
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
putchar(' ');
if (array[i][j] == 0)
putchar('.');
else
printf("%d", array[i][j]);
}
putchar('\n');
}
}
int main(void)
{
char base[SIZE][SIZE] = { 0 };
char trace[SIZE][SIZE] = { 0 };
// srand(time(0));
for (int i = 0; i < SIZE; i++)
{
for (int j = 0; j < SIZE; j++)
{
base[i][j] = (rand() % 12);
if (base[i][j] > 9)
base[i][j] = 0;
if ((rand() % 4) == 0)
base[i][j] = 5;
}
}
dump_array("Base array", SIZE, SIZE, base);
int i0 = rand() % SIZE;
int j0 = rand() % SIZE;
while (base[i0][j0] != 5)
{
i0 = rand() % SIZE;
j0 = rand() % SIZE;
}
printf("i0 = %2d, j0 = %2d, base[%2d][%2d] = %d\n", i0, j0, i0, j0, base[i0][j0]);
connectedvals(base, trace, i0, j0);
dump_array("Connected region", SIZE, SIZE, trace);
return 0;
}
输出
Base array (13x13):
7 5 5 . . . . 3 7 5 3 9 4
3 8 1 8 2 7 3 5 5 5 8 6 5
5 4 5 6 . 5 5 5 . . 7 9 5
5 3 9 5 5 3 . 5 . 4 5 9 5
5 1 5 5 5 3 . 5 . 5 5 5 .
. 5 7 5 3 2 2 4 8 . 8 3 6
5 1 3 5 6 5 . 2 7 4 2 7 1
8 . 4 5 5 7 9 . 5 . 5 . 7
5 9 5 2 . 1 5 5 3 . . 5 5
. 7 1 8 3 3 5 9 . . 3 3 3
. 5 1 5 9 9 5 8 5 2 5 . 8
4 2 9 9 . 5 5 5 . 5 2 4 3
5 2 5 2 3 5 4 1 5 9 5 5 5
i0 = 5, j0 = 3, base[ 5][ 3] = 5
Connected region (13x13):
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . 5 5 3 . . . . . . .
. . . 5 . 3 . . . . . . .
. . . 5 . 2 2 4 . . . . .
. . . 5 . . . . . . . . .
. . . 5 5 7 . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
conn11.c — 完全修复
可能还有一些改进的空间，但这是有效的。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
enum { SIZE = 13 };
extern void connectedvals(char array[SIZE][SIZE], char newarray[SIZE][SIZE], int x, int y, int value);
void connectedvals(char array[SIZE][SIZE], char newarray[SIZE][SIZE], int x, int y, int value)
{
/*printf("a[%2d][%2d] = %d\n", x, y, array[x][y]);*/
if (array[x][y] != value || newarray[x][y] != 0)
return;
newarray[x][y] = value;
if (y + 1 < SIZE)
connectedvals(array, newarray, x + 0, y + 1, value);
if (y - 1 >= 0)
connectedvals(array, newarray, x + 0, y - 1, value);
if (x + 1 < SIZE)
connectedvals(array, newarray, x + 1, y + 0, value);
if (x - 1 >= 0)
connectedvals(array, newarray, x - 1, y + 0, value);
}
static void dump_array(const char *tag, int rows, int cols, char array[rows][cols])
{
printf("%s (%dx%d):\n", tag, rows, cols);
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
putchar(' ');
if (array[i][j] == 0)
putchar('.');
else
printf("%d", array[i][j]);
}
putchar('\n');
}
}
int main(void)
{
char base[SIZE][SIZE] = { 0 };
char trace[SIZE][SIZE] = { 0 };
// srand(time(0));
for (int i = 0; i < SIZE; i++)
{
for (int j = 0; j < SIZE; j++)
{
base[i][j] = (rand() % 12);
if (base[i][j] > 9)
base[i][j] = 0;
if ((rand() % 4) == 0)
base[i][j] = 5;
}
}
dump_array("Base array", SIZE, SIZE, base);
int i0 = rand() % SIZE;
int j0 = rand() % SIZE;
while (base[i0][j0] != 5)
{
i0 = rand() % SIZE;
j0 = rand() % SIZE;
}
printf("i0 = %2d, j0 = %2d, base[%2d][%2d] = %d\n", i0, j0, i0, j0, base[i0][j0]);
connectedvals(base, trace, i0, j0, base[i0][j0]);
dump_array("Connected region", SIZE, SIZE, trace);
return 0;
}
输出
Base array (13x13):
7 5 5 . . . . 3 7 5 3 9 4
3 8 1 8 2 7 3 5 5 5 8 6 5
5 4 5 6 . 5 5 5 . . 7 9 5
5 3 9 5 5 3 . 5 . 4 5 9 5
5 1 5 5 5 3 . 5 . 5 5 5 .
. 5 7 5 3 2 2 4 8 . 8 3 6
5 1 3 5 6 5 . 2 7 4 2 7 1
8 . 4 5 5 7 9 . 5 . 5 . 7
5 9 5 2 . 1 5 5 3 . . 5 5
. 7 1 8 3 3 5 9 . . 3 3 3
. 5 1 5 9 9 5 8 5 2 5 . 8
4 2 9 9 . 5 5 5 . 5 2 4 3
5 2 5 2 3 5 4 1 5 9 5 5 5
i0 = 5, j0 = 3, base[ 5][ 3] = 5
Connected region (13x13):
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . 5 5 . . . . . . . .
. . 5 5 5 . . . . . . . .
. . . 5 . . . . . . . . .
. . . 5 . . . . . . . . .
. . . 5 5 . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
这两个程序的测试工具几乎相同。差异在于初始调用 connectedvals() 的参数列表，因为这两个实现具有不同数量的参数。
尺寸选择13并非偶然；它碰巧用随机数生成器产生了一个简洁的结果。该矩阵是“随机”生成的，只不过结果故意偏向数字 0 和 5。您很可能从计算机上的 rand() 函数得到不同的结果；我在运行 macOS 10.14.5 Mojave 的 MacBook Pro 上进行测试，使用 GCC 9.1.0 进行编译。
可以使用时间作为种子 - 取消注释一行。然而，对于初始测试，确定性(可重复性)比随机性更有利。有很多比使用时间更好的播种 rand() 的方法；这是可以预见的。然而，这样的改进超出了问题的范围。
请注意enum { SIZE = 13 };的使用。通过仅更改一个数字，整个程序就会适应新的大小。
关于c - 如何在数组中查找具有相同值的连接单元格，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/56519149/