我正在一個項目中工作，在這個項目中，我被卡住了。在C中查找二維數組中的所有相鄰元素
我的問題是例如我有以下二維數組包含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 => A A A A B => (A: 4, B: 1)
1 2 2 2 1 => C A A A B => (A: 3 + 4, B: 1 + 1, C: 1)
3 3 2 3 2 => D D A E F => (A: 1 + 7, B: 2, C: 1, D: 2, E: 1, F: 1)
3 1 3 3 1 => D G E E G => (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 <stdlib.h>
#include <string.h>
#include <stdio.h>
#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: %s\n", 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: %d\n", ele, j, i); */
if (i && (ele == eles[j][i-1])) {
/* printf(" equal to left element\n"); */
z = ref_zone(current[i-1]);
if (j && (ele == eles[j-1][i])) {
zone *z1 = last[i];
/* printf(" equal to upper element\n"); */
if (z != z1) {
int k;
/* printf(" collapsing zone %p\n", 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 element\n"); */
z = ref_zone(last[i]);
}
else {
/* printf(" new element\n"); */
z = new_zone(j, i);
}
z->acu++;
current[i] = z;
/* printf(" element zone: %p\n", 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: %d\n", best, best->row, best->col, best->acu); */
}
}
}
printf("best zone is at row: %d, col: %d, ele: %d, size: %d\n", best->row, best->col, eles[best->row][best->col], best->acu);
}
假設你的矩陣是一個圖，並且元素是頂點。如果兩個頂點相鄰且具有相同的值，則連接兩個頂點。如果您在該圖表中執行任何搜索，無論是Breadth-First Search還是Depth-First Search，都會得到您想要的。 HTH
步驟3.1-3.3應被實現爲遞歸函數，它接受座標和兩個陣列作爲參數並返回1 +的遞歸調用返回值的總和。
你可以把它看作是一個油漆應用程序中的圖片。對2D數組中的每個元素執行flood-fill（除非其已被其他東西填充），並跟蹤您在每個步驟中填充的像素數。
如果數組聲明如下
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庫將提供現成的這種功能。
請原諒我，如果在下面的代碼中，您會發現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變得更加緊湊
你嘗試過什麼構造，怎麼不工作？此外，陣列是有界的，環形的還是球形的？ – 2010-12-09 10:56:24
你在寫掃雷機嗎？ :) – 2010-12-09 10:57:19
你是否想要相鄰元素的最長鏈的數量（例如，在你的例子中是8）？或者你想讓他們在二維陣列中的位置？ – 2010-12-09 11:39:08