一個簡單的FPGA實現
使用回溯來獲取所有集羣，讓我們從（0,0）開始作爲一個例子，我們首先檢查是否（0,0）爲1，如果是這樣，檢查它的鄰居一個一個。如果其中一個鄰居是1，那麼移動並按照相同的方式進行檢查。這個過程不會停止，直到位置的四個方向鄰居全部爲0或被訪問。
要記錄我們訪問的位置，我們需要一個與原點數組大小相同的標誌圖。另外，爲了繪製每個簇，在回溯期間，我們同時記錄每個位置，我選擇一組列表來保存簇中的所有位置。
這裏是所有的代碼，包括您發表
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#define MAX_COL 6
#define MAX_ROW 5
#define MAX_SIZE (MAX_COL * MAX_ROW)
int a[5][6] = {
1, 1, 0, 0, 0, 0,
1, 1, 0, 1, 0, 0,
1, 0, 0, 0, 0, 1,
0, 0, 1, 1, 0, 1,
0, 0, 1, 0, 1, 1,
};
int dir_x[4] = {0, 1, 0, -1};
int dir_y[4] = {1, 0, -1, 0};
struct point {
int x;
int y;
};
struct node {
struct point pos;
struct node *next;
};
struct node* cluster_set[MAX_SIZE];
int cluster_set_index = 0;
int is_inside(int height, int width, int i, int j)
{
if (0 <= j && j < width && i >= 0 && i < height)
return 1;
return 0;
}
int cluster_check(int (*matrix)[MAX_COL], int height, int width, int row, int col, int (*flag_matrix)[MAX_COL], struct node* head)
{
int i, tmp_x, tmp_y;
flag_matrix[row][col] = 1;
for (i = 0; i < 4; i++)
{
tmp_x = row + dir_x[i];
tmp_y = col + dir_y[i];
if (is_inside(height, width, tmp_x, tmp_y) && matrix[tmp_x][tmp_y] && !flag_matrix[tmp_x][tmp_y]) {
flag_matrix[tmp_x][tmp_y] = 1;
struct node *new_node = (struct node*)malloc(sizeof(struct node));
assert(new_node != NULL);
new_node -> pos.x = tmp_x;
new_node -> pos.y = tmp_y;
new_node -> next = NULL;
head -> next = new_node;
cluster_check(matrix, height, width, tmp_x, tmp_y, flag_matrix, new_node);
}
}
}
int cluster_count(int (*matrix)[MAX_COL], int height, int width)
{
int count = 0, i, j;
int flag_matrix[MAX_ROW][MAX_COL] = {0};
for (i = 0; i < height; i++)
for (j = 0; j < width; j++)
{
if (matrix[i][j] && !flag_matrix[i][j]) {
count++;
struct node *new_node = (struct node*)malloc(sizeof(struct node));
assert(new_node != NULL);
new_node -> pos.x = i;
new_node -> pos.y = j;
new_node -> next = NULL;
cluster_set[cluster_set_index++] = new_node;
cluster_check(matrix, height, width, i, j, flag_matrix, new_node);
}
}
return count;
}
void print_cluster(int (*map)[MAX_COL], int row, int col)
{
int i, j;
for (i = 0; i < row; i++)
{
for (j = 0; j < col; j++)
printf("%2d ", map[i][j]);
printf("\n");
}
printf("\n");
}
int main()
{
printf("total clusters: %d\n", cluster_count(a, 5, 6));
int i, cluster_map[MAX_ROW][MAX_COL] = {0};
struct node *tmp;
for (i = 0; i < cluster_set_index; i++)
{
tmp = cluster_set[i];
while (tmp != NULL) {
printf("(%d, %d)", tmp->pos.x, tmp->pos.y);
cluster_map[tmp->pos.x][tmp->pos.y] = 1;
tmp = tmp -> next;
}
printf("\n");
print_cluster(cluster_map, MAX_ROW, MAX_COL);
memset(cluster_map, 0x00, sizeof(int)*MAX_ROW*MAX_COL);
}
}
這裏測試用例的運行結果，只是忽略你不需要
total clusters: 4
(0, 0)(0, 1)(1, 1)(1, 0)(2, 0)
1 1 0 0 0 0
1 1 0 0 0 0
1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
(1, 3)
0 0 0 0 0 0
0 0 0 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
(2, 5)(3, 5)(4, 5)(4, 4)
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1
0 0 0 0 0 1
0 0 0 0 1 1
(3, 2)(4, 2)
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 0 0
0 0 1 0 0 0
什麼是「集羣」這裏的信息來源？任何方向上都帶有相鄰的'1'的任何'1'？ – Evert
是的，但只能向左下方，不在對角線上。對於這個例子，有4個集羣。 –
儘管如此，您仍然處於正確的軌道：您可以在雙重循環中逐步瀏覽2D矩陣的元素，並且對於每個是1的元素，都可以上下左右（「+1」 '，'-1'到行或列索引）以查看它是否包含'1'。有可能更聰明的方式，但這將是最直接的方式。您需要另一個矩陣來跟蹤已屬於某個集羣的元素。 – Evert