| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 100539 | salepark | 보물 찾기 (CEOI13_treasure2) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "treasure.h"
bool visit[101][101];
int V;
void check(int a, int b, int c, int d) {
for (int i = a; i <= c; i++) {
for (int j = b; j <= d; j++) {
visit[i][j] = 1;
}
}
}
void end() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (visit[i][j] == 1) Report(i, j);
}
}
exit(0);
}
void go(int a, int b, int N, int C) {
int M = N % 2 == 0 ? N / 2 : (N / 2) + 1;
int v = C;
if (C == 0) {
end();
}
if (M == 1) {
if (countTreasure(a, b, a, b) == 1) {
visit[a][b] = 1;
v--;
if (v == 0) end();
}
if (countTreasure(a + 1, b, a + 1, b) == 1) {
visit[a + 1][b] = 1;
C--;
if (v == 0) end();
}
if (countTreasure(a, b + 1, a, b + 1) == 1) {
visit[a][b + 1] = 1;
v--;
if (v == 0) end();
}
if (countTreasure(a + 1, b + 1, a + 1, b + 1) == 1) {
visit[a + 1][b + 1] = 1;
v--;
if (v == 0) end();
}
return;
}
if (N % 2 == 0) {
int cnt = countTreasure(a, b, a + M - 1, b + M - 1);
if (cnt == M * M) {
v -= M * M;
check(a, b, a + M - 1, b + M - 1);
}
else if (cnt == 0) return;
else go(a, b, M, v);
cnt = countTreasure(a + M, b, a + (2 * M) - 1, b + M - 1);
if (cnt == M * M) {
v -= M * M;
check(a + M, b, a + (2 * M) - 1, b + M - 1);
}
else if (cnt == 0) return;
else go(a + M, b, M, v);
cnt = countTreasure(a, b + M, a + M - 1, b + (2 * M) - 1);
if (cnt == M * M) {
v -= M * M;
check(a, b + M, a + M - 1, b + (2 * M) - 1);
}
else if (cnt == 0) return;
else go(a, b + M, M, v);
cnt = countTreasure(a + M, b + M, a + (2 * M) - 1, b + (2 * M) - 1);
if (cnt == M * M) {
v -= M * M;
check(a + M, b + M, a + (2 * M) - 1, b + (2 * M) - 1);
}
else if (cnt == 0) return;
else go(a + M, b + M, M, v);
}
else {
int cnt = countTreasure(a, b, a + M - 1, b + M - 1);
if (cnt == M * M) {
v -= M * M;
check(a, b, a + M - 1, b + M - 1);
}
else if (cnt == 0) return;
else go(a, b, M, v);
cnt = countTreasure(a + M - 1, b, a + (2 * M) - 2, b + M - 1);
if (cnt == M * M) {
v -= M * M;
check(a + M - 1, b, a + (2 * M) - 2, b + M - 1);
}
else if (cnt == 0) return;
else go(a + M - 1, b, M, v);
cnt = countTreasure(a, b + M - 1, a + M - 1, b + (2 * M) - 2);
if (cnt == M * M) {
v -= M * M;
check(a, b + M - 1, a + M - 1, b + (2 * M) - 2);
}
else if (cnt == 0) return;
else go(a, b + M - 1, M, v);
cnt = countTreasure(a + M - 1, b + M - 1, a + (2 * M) - 2, b + (2 * M) - 2);
if (cnt == M * M) {
v -= M * M;
check(a + M - 1, b + M - 1, a + (2 * M) - 2, b + (2 * M) - 2);
}
else if (cnt == 0) return;
else go(a + M - 1, b + M - 1, M, v);
}
}
void findTreasure(int N) {
V = countTreasure(1, 1, N, N);
if (V == 0) return;
else if (V == N * N) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
Report(i, j);
}
}
}
else {
go(1, 1, N, V);
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (visit[i][j] == 1) Report(i, j);
}
}
}