4連結ラベリング/C++

4連結ラベリング一番簡単なアルゴリズムを記述します

const int dx[] = { +1, 0, -1, 0 };
const int dy[] = { 0, +1, 0, -1 };

// matrix dimensions
int row_count=5;
int col_count=5;
const int w = 5, h = 5;
int input[w][h] = { {1,0,0,0,1},
					{1,1,0,1,1},
					{0,1,0,0,1},
					{1,1,1,1,0},
					{0,0,0,1,0} };


// the labels, 0 means unlabeled
int label[w][h];
void find_components();
int main();
void dfs(int x, int y, int current_label);

int main()
{
	find_components();
	std::cout << "Hello World!\n";
	for (int i = 0; i < 5; i++)
	{
		for (int j = 0;j < 5; j++)
		{
			std::cout << label[i][j];
		}
		std::cout << "\n";
	}
}




void dfs(int x, int y, int current_label) {
	if (x < 0 || x == row_count) return; // out of bounds
	if (y < 0 || y == col_count) return; // out of bounds
	if (label[x][y] || !input[x][y]) return; // already labeled or not marked with 1 in m

	// mark the current cell
	label[x][y] = current_label;

	// recursively mark the neighbors
	for (int direction = 0; direction < 4; ++direction)
		dfs(x + dx[direction], y + dy[direction], current_label);
}

void find_components() {
	int component = 0;
	for (int i = 0; i < row_count; ++i)
		for (int j = 0; j < col_count; ++j)
			if (!label[i][j] && input[i][j]) dfs(i, j, ++component);
}