티스토리 뷰
[ 해결 방법 ]
시작 점부터 끝점까지 이중 for문을 돌면서 모두 색이 같은지 판단합니다. 만약 색이 다르다면 이중 for문을 돌던 영역을 9등분해서 다시 이중 for문을 돕니다. 모두 같은 숫자의 종이가 될 때까지 계속 돌면 문제를 해결할 수 있습니다.
[ 코드 ]
#include <iostream>#define MAX 2500using namespace std;struct point{int x, y;};int N, Type[3];int board[MAX][MAX];void InData(){cin >> N;for(int i = 1; i <= N; i++)for(int j = 1; j <= N; j++)cin >> board[i][j];}void DQ(point from, point to){int pcr, cr;pcr = board[from.y][from.x];for(int y = from.y; y <= to.y; y++){for(int x = from.x; x <= to.x; x++){cr = board[y][x];if(pcr != cr){int seg = (to.x - from.x + 1) / 3;int limit_y = to.y - seg + 1;int limit_x = to.x - seg + 1;for(int ny = from.y; ny <= limy; ny += seg){for(int nx = from.x; nx <= limit_x; nx += seg)DQ(point{nx, ny}, point{nx + seg - 1, ny + seg - 1});}return;}pcr = cr;}}Type[cr + 1]++;}int main(){InData();DQ(point{1,1}, point{N, N});for(int i = 0; i < 3; i++)cout << Type[i] << endl;;return 0;}
'알고리즘 > 분할정복' 카테고리의 다른 글
백준_하노이 탑 이동 순서 (0) | 2016.09.20 |
---|---|
백준_쿼드트리 (0) | 2016.09.16 |