#include "treasure.h"
#define MAX_N 100
int front;
int rear;
int shouldBeHere[105][105] = { 0, };
typedef struct {
int r1, c1, r2, c2, t;
}pos;
pos queue[MAX_N];
void queueInit(void) {
front = 0;
rear = 0;
}
int queueIsEmpty(void) {
return (front == rear);
}
int queueIsFull(void) {
if ((rear + 1) % MAX_N == front) {
return 1;
}
else {
return 0;
}
}
int queueEnqueue(pos value) {
if (queueIsFull()) {
return 0;
}
queue[rear] = value;
rear++;
if (rear == MAX_N) {
rear = 0;
}
return 1;
}
int queueDequeue(pos* value) {
if (queueIsEmpty()) {
return 0;
}
*value = queue[front];
front++;
if (front == MAX_N) {
front = 0;
}
return 1;
}
void findTreasure(int N) {
int cnt = countTreasure(1, 1, N, N);
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
shouldBeHere[i][j] = 0;
}
}
if (cnt > 0) {
queueInit();
pos first;
first.r1 = 1;
first.c1 = 1;
first.r2 = N;
first.c2 = N;
first.t = cnt;
queueEnqueue(first);
while (!queueIsEmpty()) {
pos now;
queueDequeue(&now);
if (now.r1 == now.r2 && now.c1 == now.c2) {
shouldBeHere[now.r1][now.c1] = 1;
}
else {
int numT = now.t;
int center_r = (now.r1 + now.r2) / 2;
int center_c = (now.c1 + now.c2) / 2;
int foundHere = 0;
if (numT > 0) {
foundHere = countTreasure(now.r1, now.c1, center_r, center_c);
if (foundHere) {
pos left_up;
left_up.r1 = now.r1;
left_up.c1 = now.c1;
left_up.r2 = center_r;
left_up.c2 = center_c;
left_up.t = foundHere;
numT -= foundHere;
queueEnqueue(left_up);
}
}
if (numT > 0) {
if (now.c2 >= center_c + 1) {
foundHere = countTreasure(now.r1, center_c + 1, center_r, now.c2);
if (foundHere) {
pos right_up;
right_up.r1 = now.r1;
right_up.c1 = center_c + 1;
right_up.r2 = center_r;
right_up.c2 = now.c2;
right_up.t = foundHere;
numT -= foundHere;
queueEnqueue(right_up);
}
}
}
if (numT > 0) {
if (now.r2 >= center_r + 1) {
foundHere = countTreasure(center_r + 1, now.c1, now.r2, center_c);
if (foundHere) {
pos left_down;
left_down.r1 = center_r + 1;
left_down.c1 = now.c1;
left_down.r2 = now.r2;
left_down.c2 = center_c;
left_down.t = foundHere;
numT -= foundHere;
queueEnqueue(left_down);
}
}
}
if (numT > 0) {
foundHere = 0;
if (now.r2 >= center_r + 1 && now.c2 >= center_c + 1) {
pos right_down;
right_down.r1 = center_r + 1;
right_down.c1 = center_c + 1;
right_down.r2 = now.r2;
right_down.c2 = now.c2;
right_down.t = numT;
queueEnqueue(right_down);
}
}
}
}
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (shouldBeHere[i][j]) {
Report(i, j);
}
}
}
}
/*
10
1011010101
1100010001
0100100101
0000101100
1111010100
0010100000
1101010001
0001010100
0101000100
1101010101
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
0 ms |
364 KB |
Output is partially correct - N = 5, K = 624, score = 1 |
| 2 |
Partially correct |
0 ms |
364 KB |
Output is partially correct - N = 10, K = 9723, score = 1 |
| 3 |
Incorrect |
0 ms |
364 KB |
Error - not all of the treasure cells have been reported |
| 4 |
Incorrect |
0 ms |
364 KB |
Error - not all of the treasure cells have been reported |
| 5 |
Incorrect |
1 ms |
364 KB |
Error - not all of the treasure cells have been reported |
| 6 |
Incorrect |
1 ms |
364 KB |
Error - not all of the treasure cells have been reported |
| 7 |
Incorrect |
1 ms |
364 KB |
Error - not all of the treasure cells have been reported |
| 8 |
Incorrect |
1 ms |
364 KB |
Error - not all of the treasure cells have been reported |
| 9 |
Incorrect |
1 ms |
364 KB |
Error - not all of the treasure cells have been reported |
| 10 |
Incorrect |
1 ms |
364 KB |
Error - not all of the treasure cells have been reported |
