我正在开展一个项目,我一度陷入困境。
我的问题是例如我有以下2D数组包含3个不同的整数。
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
我想要的是找到数组中包含的任何数字的数组的最长的相邻元素链。
与上面的数组一样,最长的链是数字2。
2 2 2 2 2 2 2 2
任何人都可以指导我为实现这一目标必须做些什么吗?
谢谢。
绘制比解释更容易…
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)!
以上就是c/c++开发分享在C中查找2D数组中的所有相邻元素相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/979179.html