Counting cells in a Blob_v1 c++

3552 ワード
recursion DFS algorithm テキストリンク
まずnhn pre-test 1シミュレーションテストの例を見て、それから急いで以前の学校で勉強したことを整理し直します!
これは私がRecursionを勉強したときに主に議論した内容です.
サイズ8 x 8のマトリクス
{1,0,0,0,0,0,0,1},
{0,1,1,0,0,1,0,0},
{1,1,0,0,1,0,1,0},
{0,0,0,0,0,1,0,0},
{0,1,0,1,0,1,0,0},
{0,1,0,1,0,1,0,0},
{1,0,0,0,1,0,0,1},
{0,1,1,0,0,1,1,1},
これがあったと思ってください.
ここでの問題は、隣接する1を1つのBlobに結合し、各Blobにおいてセルの数を計算することである.

図に示すように、4つのBlobがあり、各Blobには5、1、13、5つのセルがあります.
まず、現在のピクセルが属するBlobのサイズを計算するには
1. x,y=!1はreturn 0を表します(シェーディングセルでない場合はreturn 0)
2.x、y=1の場合、現在の画素をカウントする
2-1. 現在のピクセルを繰り返しカウントしないように表示(カウント)
2-2. 現在のピクセルに隣接するすべてのピクセルについて、そのピクセルが属するblobのサイズを計算し、カウンタに追加します.
  • x,y座標を選択し、Blobに何個のセルがあるかを求めるコード
    • #include<stdio.h>

const int N = 8;

int grid[8][8] = {
	{1,0,0,0,0,0,0,1},
	{0,1,1,0,0,1,0,0},
	{1,1,0,0,1,0,1,0},
	{0,0,0,0,0,1,0,0},
	{0,1,0,1,0,1,0,0},
	{0,1,0,1,0,1,0,0},
	{1,0,0,0,1,0,0,1},
	{0,1,1,0,0,1,1,1},
};

const int BACKGROUND_COLOUR = 0;
const int IMANGE_COLOUR = 1;
const int ALREADY_COUNTED = 2;

int countCells(int x, int y) {
	if (x < 0 || y<0 || x >= N || y>N)
		return 0;

	else if (grid[x][y] != IMANGE_COLOUR)
		return 0;

	else {
		grid[x][y] = ALREADY_COUNTED;

		return 1 + countCells(x, y - 1) + countCells(x + 1, y - 1) + countCells(x + 1, y)
			+ countCells(x + 1, y + 1) + countCells(x, y + 1) + countCells(x - 1, y + 1)
			+ countCells(x - 1, y) + countCells(x - 1, y - 1);
	}
}

int main() {
	int x, y;

	printf("insert the x,y point : ");
	scanf_s("%d %d", &x, &y);
	printf("It has %d bolocks in this Blob. \n", countCells(x, y));

	return 0;
}
  • コード
    • 、いくつかのBlobがあり、各Blobにはいくつかのセルがあります.
    #include<iostream>
#include<vector>

using namespace std;

const int N = 8;
vector<int> list(N);
int nList = 0;

int grid[8][8] = {
	{1,0,0,0,0,0,0,1},
	{0,1,1,0,0,1,0,0},
	{1,1,0,0,1,0,1,0},
	{0,0,0,0,0,1,0,0},
	{0,1,0,1,0,1,0,0},
	{0,1,0,1,0,1,0,0},
	{1,0,0,0,1,0,0,1},
	{0,1,1,0,0,1,1,1},
};

const int BACKGROUND_COLOUR = 0;
const int	 IMANGE_COLOUR = 1;
const int ALREADY_COUNTED = 2;

int countCells(int x, int y) {
	if (x < 0 || y<0 || x >= N || y>=N)
		return 0;

	else if (grid[x][y] != IMANGE_COLOUR)
		return 0;

	else {
		grid[x][y] = ALREADY_COUNTED;

		return 1 + countCells(x, y - 1) + countCells(x + 1, y - 1) + countCells(x + 1, y)
			+ countCells(x + 1, y + 1) + countCells(x, y + 1) + countCells(x - 1, y + 1)
			+ countCells(x - 1, y) + countCells(x - 1, y - 1);
	}
}

void solution() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (grid[i][j] == IMANGE_COLOUR) {
				list[nList++]=countCells(i, j);
			}
		}
	}

	cout << nList << endl;
	for (int i = 0; i < nList; i++) 
		cout << list[i] << " ";

}

int main() {

	solution();

	return 0;
}
    TIL-031 | Django_Project Setting
    [Oracle]単一関数-日付関数