분할정복 문제이다. 반복문을 써도 되겠지만 재귀함수가 좀 더 만들기 쉬워서 재귀함수를 사용했다.
종이를 계속 4등분해 나가다가 면이 채워진게 확인되면 리턴하는 재귀함수를 만든다.
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int arr[129][129];
int n;
int check_res(int num,int x,int y) {
int chk = arr[x][y];
for(int i = x;i<num+x;i++) {
for(int j = y;j<num+y;j++) {
if(chk != arr[i][j]) return 0;
}
}
if(chk == 0) {
return 1;
}
if(chk == 1) {
return 2;
}
}
int res1 = 0,res2=0;
void func(int num,int x,int y) {
if(num == 1) {
if(arr[x][y] == 1) res2++;
else res1++;
return;
}
int tmp = check_res(num,x,y);
if(tmp == 1) {
res1++;
return;
}
if(tmp == 2) {
res2++;
return;
}
for(int i = 0;i<2;i++) {
for(int j = 0;j<2;j++) {
func(num/2,x+num/2*i,y+num/2*j);
}
}
}
int main() {
scanf("%d",&n);
for(int i = 0;i<n;i++) {
for(int j = 0;j<n;j++) {
scanf("%d",&arr[i][j]);
}
}
func(n,0,0);
printf("%d\n%d",res1,res2);
}