제출 #94887

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
94887		emphasis10	보물 찾기 (CEOI13_treasure2)	C++14	0 / 100	352 ms	263168 KiB

treasure

#include "treasure.h"

int tmap[101][101]; //-1 : unknown 0 : no treasure 1: treasure
int dir[2][4] = { {0,0,-1,1}, {1, -1, 0,0} };
int myN;

int totaltreasure;

void ecofind(int x1, int y1, int x2, int y2) {
	if (totaltreasure == 0) return;
	if (x1 == x2 && y1 == y2) {
		for (int i = 0; i < 4; i++) {
			int nx = x1 + dir[0][i];
			int ny = y1 + dir[1][i];
			if (nx >= 1 && nx <= myN && ny >= 1 && ny <= myN) {
				if (tmap[nx][ny] == 1) {
					int a, b, c, d;
					if (x1 < nx) { a = x1, c = nx; }
					else { a = nx, c = x1; }
					if (y1 < ny) { b = y1, d = ny; }
					else { b = ny, d = y1; }
					tmap[x1][y1] = countTreasure(a, b, c, d) - 1;
					if (tmap[x1][x2] == 1) --totaltreasure;
					return;
				}
			}
		}
		tmap[x1][y1] = countTreasure(x1, y1, x2, y2);
		if (tmap[x1][x2] == 1) --totaltreasure;
		return;
	}
	int cnt = countTreasure(x1, y1, x2, y2);
	if (cnt == 0) return;
	if (cnt == (x2 - x1 + 1)*(y2 - y1 + 1)) {
		for (int i = x1; i <= x2; i++) {
			for (int j = y1; j <= y2; j++) tmap[i][j] = 1;
		}
		totaltreasure -= (x2 - x1 + 1)*(y2 - y1 + 1);
	}
	else {
		int mid = (x1 + x2) / 2;
		ecofind(x1, y1, mid, mid);
		ecofind(mid + 1, y1, x2, mid);
		ecofind(x1, mid + 1, mid, y2);
		ecofind(mid + 1, mid + 1, x2, y2);
	}
}

void findTreasure(int N) {
	for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) tmap[i][j] = -1;
	myN = N;
	totaltreasure = countTreasure(1, 1, N, N);
	if (totaltreasure == 0) return;
	if (N == 1) {
		if (countTreasure(1, 1, 1, 1) == 1) Report(1, 1);
		return;
	}
	
	if (N % 2 == 0) {
		int mid = (1 + N) / 2;
		ecofind(1, 1, mid, mid);
		ecofind(mid + 1, 1, N, mid);
		ecofind(1, mid + 1, mid, N);
		ecofind(mid + 1, mid + 1, N, N);
	}
	else {
		int mid = N / 2;
		ecofind(1, 1, mid, mid);
		ecofind(mid + 1, 1, N-1, mid);
		ecofind(1, mid + 1, mid, N - 1);
		ecofind(mid + 1, mid + 1, N - 1, N - 1);
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (tmap[i][j] == -1) tmap[i][j] = countTreasure(i, j, i, j);
		}
	}

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

• Subtask 1: 0 / 100