백준1780 종이의 개수

작성일 | In

문제 링크

  • http://icpc.me/1780

사용 알고리즘

  • 분할정복

풀이

이 문제는 데이터를 계속해서 9등분하며 탐색을 하는 문제입니다.
현재 탐색 중인 공간이 모두 같은 숫자로 이루어지지 않았다면 그 공간을 9등분해서 다시 탐색을 하면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;

int arr[3000][3000];
int a, b, c;

void f(int si, int sj, int n){
	int cur = arr[si][sj];
	bool flag = true;
	for(int i=si; i<si+n; i++){
		for(int j=sj; j<sj+n; j++){
			if(arr[i][j] != cur) flag = false;
		}
	}
	if(flag){
		if(cur == -1) a++;
		if(cur == 0) b++;
		if(cur == 1) c++;
	}
	else{
		for(int i=0; i<3; i++) for(int j=0; j<3; j++) f(si+i*n/3, sj+j*n/3, n/3);
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) cin >> arr[i][j];
	f(1, 1, n);
	cout << a << "\n" << b << "\n" << c;
}