c/c++语言开发共享在C中查找2D数组中的所有相邻元素

绘制比解释更容易…

 2 2 2 2 1 => AAAAB => (A: 4, B: 1) 1 2 2 2 1 => CAAAB => (A: 3 + 4, B: 1 + 1, C: 1) 3 3 2 3 2 => DDAEF => (A: 1 + 7, B: 2, C: 1, D: 2, E: 1, F: 1) 3 1 3 3 1 => DGEEG => (A: 8, B: 2, C: 1, D: 2 + 1, E: 2 + 1, F: 1, G: 1) 1 1 2 3 1 => ... 1 3 1 3 3 => ... 

更新 ：

现在，有了一些真正的代码：

 #include  #include  #include  #define ROWS 6 #define COLS 5 unsigned char eles[ROWS][COLS] = { { 2, 2, 2, 2, 1 }, { 1, 2, 2, 2, 1 }, { 3, 3, 2, 3, 2 }, { 3, 1, 3, 3, 1 }, { 1, 1, 2, 3, 1 }, { 1, 3, 1, 3, 3 } }; struct zone { int acu; int row, col; int refs; }; typedef struct zone zone; zone * new_zone(int row, int col) { zone *z = (zone *)malloc(sizeof(zone)); z->col = col; z->row = row; z->refs = 1; z->acu = 0; } void croak (const char *str) { fprintf(stderr, "error: %sn", str); exit(1); } void free_zone(zone *z) { if (z->refs != 0) croak("free_zone: reference count is not cero"); free(z); } zone * ref_zone(zone *z) { z->refs++; return z; } void unref_zone(zone *z) { z->refs--; if (!z->refs) free_zone(z); } int main() { zone *last[COLS]; zone *current[COLS]; zone *best = new_zone(0, 0); int i, j; memset(last, 0, sizeof(last)); for (j = 0; j < ROWS; j++) { for (i = 0; i < COLS; i++) { unsigned int ele = eles[j][i]; zone *z; /* printf("analyzing ele: %d at row %d, col: %dn", ele, j, i); */ if (i && (ele == eles[j][i-1])) { /* printf(" equal to left elementn"); */ z = ref_zone(current[i-1]); if (j && (ele == eles[j-1][i])) { zone *z1 = last[i]; /* printf(" equal to upper elementn"); */ if (z != z1) { int k; /* printf(" collapsing zone %pn", z1); */ z->acu += z1->acu; for (k = 0; k < COLS; k++) { if (last[k] == z1) { last[k] = ref_zone(z); unref_zone(z1); } } for (k = 0; k < i; k++) { if (current[k] == z1) { current[k] = ref_zone(z); unref_zone(z1); } } } } } else if (j && (ele == eles[j-1][i])) { /* printf(" equal to upper elementn"); */ z = ref_zone(last[i]); } else { /* printf(" new elementn"); */ z = new_zone(j, i); } z->acu++; current[i] = z; /* printf(" element zone: %pn", z); */ } for (i = 0; i < COLS; i++) { if (j) unref_zone(last[i]); last[i] = current[i]; if (best->acu < current[i]->acu) { unref_zone(best); best = ref_zone(current[i]); /* printf("best zone changed to %p at row; %d, col: %d, acu: %dn", best, best->row, best->col, best->acu); */ } } } printf("best zone is at row: %d, col: %d, ele: %d, size: %dn", best->row, best->col, eles[best->row][best->col], best->acu); } 

假设您的矩阵是图形，并且元素是顶点。 如果它们相邻且具有相同的值，则连接两个顶点。 如果您在该图表中执行任何搜索，无论是广度优先搜索还是深度优先搜索 ，您都可以得到您想要的内容。 HTH

步骤3.1-3.3应该实现为一个递归函数，它将坐标和两个数组作为参数，并返回1 +递归调用返回值的总和。

您可以将其视为绘画应用程序中的图片。 对2Darrays中的每个元素执行泛光填充 （除非它已被其他元素填充）并跟踪每个步骤中填充的像素数。

如果您的数组声明为

 int elements[5][5]; 

然后引入第二个数组，告诉你是否已经填充了一个元素（如果你愿意的话，使用不同的类型，比如bool如果你的C程序没问题）：

 int pixelFilled[5][5]; memset( pixelFilled, 0, sizeof( pixelFilled ) ); 

接下来，编写一个递归函数，它执行泛洪填充并返回填充的元素数量（我从头顶写这个，不保证这个函数的工作原理）：

 int floodFill( int x, int y ) { int filledPixels = 0; if ( !pixelFilled[x][y] ) { ++filledPixels; pixelFilled[x][y] = 1; } if ( x < 4 && elements[x+1][y] == elements[x][y]) filledPixels += floodFill( x + 1, y ); if ( x > 0 && elements[x-1][y] == elements[x][y] ) filledPixels += floodFill( x - 1, y ); if ( y < 4 && elements[x][y+1] == elements[x][y]) filledPixels += floodFill( x, y + 1 ); if ( y > 0 && elements[x][y-1] == elements[x][y]) filledPixels += floodFill( x, y - 1 ); return filledPixels; } 

最后，迭代你的数组并尝试完全填充它。 跟踪最大的填充数组：

 int thisArea = 0; int largestArea = 0; int x, y; for ( y = 0; y < 5; ++y ) { for ( x = 0; x < 5; ++x ) { thisArea = floodFill( x, y ); if (thisArea > largestArea ) { largestArea = thisArea; } } } 

现在， largestArea应该包含相邻元素最长链的大小。

我喜欢这种问题:-)所以这是我的答案。 正如Frerich Raabe所说，这可以通过floodFill函数来解决。 例如， opencv库将提供现成的这样的function。

请原谅我，如果在下面的代码中你会发现C ++的痕迹，以防它们应该很容易被替换。

 typedef struct Point { int x; int y; } Point; int areaOfBiggestContiguousRegion(int* mat,int nRows, int nCols) { int maxArea = 0; int currValue, queueSize, queueIndex; int* aux; Point queue[1000]; //Stores the points I need to label Point newPoint, currentPoint; int x,y,x2,y2; //Code: allocate support array aux of same size of mat //Code: fill aux of zeros for (y = 0; y < nRows; y++) for (x = 0; x < nCols; x++) if (aux[y * nCols + x] == 0) {//I find a pixel not yet labeled, my seed for the next flood fill queueIndex = 0; //Contains the index to the next element in the queue queueSize = 0; currValue = mat[y * nCols + x]; //The "color" of the current spot aux[y * nCols + x] = 1; newPoint.x = x; newPoint.y = y; queue[queueSize] = newPoint; queueSize++; while(queueIndex != queueSize) { currPoint = queue[queueIndex]; queueIndex++; //Look left, right, up, down x2 = currPoint.x - 1; y2 = currPoint.y; //Some copy & paste, sorry I have been too long on C++ to remember correctly about C functions if (x2 >= 0 && aux[y2 * nCols + x2] == 0 && mat[y2 * nCols + x2] == currValue) { aux[y2 * nCols + x2] = 1; newPoint.x = x2; newPoint.y = y2; queue[queueSize] = newPoint; queueSize++; } x2 = currPoint.x + 1; y2 = currPoint.y; //Some copy & paste, sorry I have been too long on C++ to remember correctly about C functions if (x2 < nCols && aux[y2 * nCols + x2] == 0 && mat[y2 * nCols + x2] == currValue) { aux[y2 * nCols + x2] = 1; newPoint.x = x2; newPoint.y = y2; queue[queueSize] = newPoint; queueSize++; } x2 = currPoint.x; y2 = currPoint.y - 1; //Some copy & paste, sorry I have been too long on C++ to remember correctly about C functions if (y2 >= 0 && aux[y2 * nCols + x2] == 0 && mat[y2 * nCols + x2] == currValue) { aux[y2 * nCols + x2] = 1; newPoint.x = x2; newPoint.y = y2; queue[queueSize] = newPoint; queueSize++; } x2 = currPoint.x; y2 = currPoint.y + 1; //Some copy & paste, sorry I have been too long on C++ to remember correctly about C functions if (y2 < nRows && aux[y2 * nCols + x2] == 0 && mat[y2 * nCols + x2] == currValue) { aux[y2 * nCols + x2] = 1; newPoint.x = x2; newPoint.y = y2; queue[queueSize] = newPoint; queueSize++; } } //while if (queueSize > maxArea) maxArea = queueSize; //If necessary we could store other details like currentValue }//if (aux... return maxArea; } 

注意：在C ++中使用std容器和Point的构造函数，它变得更加紧凑

需要了解更多c/c++开发分享在C中查找2D数组中的所有相邻元素，也可以关注C/ C++技术分享栏目—计算机技术网(www.ctvol.com)!