제출 #130827

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
130827		yeonwan	보물 찾기 (CEOI13_treasure2)	C++14	44 / 100	2 ms	508 KiB

treasure

#include "treasure.h"
//#include<iostream>
//using namespace std;
int ans[103][103];
int sum[103][103];

void exhaustive_Search(int N) {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) if (countTreasure(i, j, i, j)) ans[i][j] = 1;
	}
}


void recursively_find(int a, int b, int c, int d) { //(a,b) ~ (c,d) 까지.	
	int cnt = countTreasure(a, b, c, d);
	if (cnt == 0) return;
	if ((a - c) + (b - d) == 1 && cnt == 1) {
		if (countTreasure(a, b, a, b)) ans[a][b] = 1;
		else ans[c][d] = 1;
		return;
	}

	if (cnt == (c - a + 1) * (d - b + 1)) {
		for (int i = a; i <= c; i++) {
			for (int j = b; j <= d; j++) ans[i][j] = 1;
		}
		return;
	}
	
	if (a == c && b == d) return;
	
	int depth = c - a ;
	int width = d - b ;
	
	if (depth >= width) {  // 세로 >= 가로
		
		recursively_find(a, b, a + depth/2, d);
		recursively_find(a + depth/2+1, b , c, d);
	}
	else { // 가로 > 세로
		recursively_find(a, b, c,  b+ width/2 );
		recursively_find(a, b + width/2 + 1 , c, d);
	}
	
}

void findbyArea(int N) {
	
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			sum[i][j] = countTreasure(1, 1, i, j);
			ans[i][j] = sum[i][j] - sum[i - 1][j] - sum[i][j - 1] + sum[i - 1][j - 1];
		}
	}

}



void findTreasure(int N) {
	//recursively_find(1, 1, N, N);
	//exhaustive_Search(N);
	findbyArea(N);
	

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (ans[i][j]) Report(i, j);
		}
	}
}

• Subtask 1: 44 / 100