Counting cells in a Blob_v1 c++
nhn pre-test1 모의 테스트 예시 보다가 예전에 학교 다닐 때 공부했던 걸 급하게 다시 정리한다!
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들을 한 Blob 으로 묶고 Blob의 갯수와 각 Blob안에 cell의 갯수를 카운트 하는 문제다.
그림을 보면 총 4개의 Blob이 있고 각 Blob에는 5, 1, 13, 5 개의 cell이 있다.
먼저 현재 픽셀이 속한 Blob의 크기를 카운트 하려면
1. x,y=!1이면 return 0 (색칠된 칸이 아니면 return 0)
2. x,y=1 이면 현재 픽셀을 카운트
2-1. 현재 픽셀이 중복 카운트 되는 것을 막기 위해 표시 (already counted)
2-2. 현재 픽셀에 이웃한 모든 픽셀들에 대해 그 픽셀이 속한 blob의 크기를 카운트하여 카운터에 더해줌.
- x,y 좌표를 선택하고 해당 Blob에 몇 개의 Cell이 있는지 구하는 코드
#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에 몇 개의 Cell이 있는지 구하는 코드
#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;
}
Author And Source
이 문제에 관하여(Counting cells in a Blob_v1 c++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimmy/Counting-cells-in-a-Blobv1-c저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)