Contest Duration: - (local time) (90 minutes) Back to Home

Submission #19360

Source Code Expand

Copy
```#include <stdio.h>
#include <stdlib.h>

#define A int
#define B int

typedef struct {
A first;
B second;
} pair;

int cmp_first(A a, A b)
{
return a - b;
}

int cmp_second(B a, B b)
{
return a - b;
}

int cmp_pair(pair a, pair b)
{
int x = cmp_first(a.first, b.first);

if (x != 0) return x;

return cmp_second(a.second, b.second);
}

pair make_pair(A first, B second)
{
pair p;

p.first = first;
p.second = second;

return p;
}

#define Q pair

typedef struct _queue {
Q value;
int size;
struct _queue *next;
struct _queue *last;
} queue;

queue *push(queue *q, Q value)
{
queue *tmp = malloc(sizeof(queue));

tmp->value = value;
tmp->next = NULL;
tmp->last = tmp;

if (q == NULL) {
tmp->size = 1;

return tmp;
} else {
q->size++;

q->last->next = tmp;
q->last = tmp;

return q;
}
}

queue *pop(queue *q)
{
if (q->size == 1) {
free(q);

return NULL;
} else {
queue *tmp = q->next;

tmp->size = q->size - 1;
tmp->last = q->last;

free(q);

return tmp;
}
}

Q front(queue *q)
{
return q->value;
}

Q back(queue *q)
{
return q->last->value;
}

int empty(queue *q)
{
if (q == NULL) {
return 1;
} else {
return 0;
}
}

int size(queue *q)
{
if (empty(q)) {
return 0;
} else {
return q->size;
}
}

void clear(queue *q)
{
if (q->next != NULL) clear(q->next);

free(q);
}

int n, m, x1, y1, x2, y2;
char s[500][501];
double a[250001];
int f[500][500];

int dfs(int x, int y)
{
f[x][y] = 1;

if (x == x2 && y == y2) return 1;

if (x > 0 && s[x - 1][y] != '#' && f[x - 1][y] == 0) {
if (dfs(x - 1, y) == 1) return 1;
}

if (x < n - 1 && s[x + 1][y] != '#' && f[x + 1][y] == 0) {
if (dfs(x + 1, y) == 1) return 1;
}

if (y > 0 && s[x][y - 1] != '#' && f[x][y - 1] == 0) {
if (dfs(x, y - 1) == 1) return 1;
}

if (y < m - 1 && s[x][y + 1] != '#' && f[x][y + 1] == 0) {
if (dfs(x, y + 1) == 1) return 1;
}

return 0;
}

int ok(double c)
{
int i, j;
queue *q = NULL;

for (i = 0; i < n; i++) {
for (j = 0; j < m; j++) {
f[i][j] = 0;
}
}

q = push(q, make_pair(x1 * 500 + y1, 0));

while (!empty(q)) {
pair p = front(q);
int x, y, t;

q = pop(q);

x = p.first / 500;
y = (p.first - x * 500) % m;
t = p.second + 1;

if (f[x][y] == 1) continue;

f[x][y] = 1;

if (x == x2 && y == y2) return 1;

if (x > 0 && s[x - 1][y] != '#' && f[x - 1][y] == 0) {
if ((s[x - 1][y] - '0') * a[t] >= c) {
q = push(q, make_pair((x - 1) * 500 + y, t));
}
}

if (x < n - 1 && s[x + 1][y] != '#' && f[x + 1][y] == 0) {
if ((s[x + 1][y] - '0') * a[t] >= c) {
q = push(q, make_pair((x + 1) * 500 + y, t));
}
}

if (y > 0 && s[x][y - 1] != '#' && f[x][y - 1] == 0) {
if ((s[x][y - 1] - '0') * a[t] >= c) {
q = push(q, make_pair(x * 500 + y - 1, t));
}
}

if (y < m - 1 && s[x][y + 1] != '#' && f[x][y + 1] == 0) {
if ((s[x][y + 1] - '0') * a[t] >= c) {
q = push(q, make_pair(x * 500 + y + 1, t));
}
}
}

return 0;
}

int main()
{
int i, j;
double l, r, mid;

scanf("%d %d", &n, &m);

for (i = 0; i < n; i++) scanf("%s", s[i]);

for (i = 0; i < n; i++) {
for (j = 0; j < m; j++) {
if (s[i][j] == 's') {
x1 = i;
y1 = j;
} else if (s[i][j] == 'g') {
x2 = i;
y2 = j;
}
}
}

a[0] = 1;

for (i = 1; i <= n * m; i++) a[i] = a[i - 1] * 0.99;

for (i = 0; i < n; i++) {
for (j = 0; j < m; j++) {
f[i][j] = 0;
}
}

if (dfs(x1, y1) == 0) {
puts("-1");

return 0;
}

l = 0;
r = 10;
mid = (l + r) / 2;

for (i = 0; i < 50; i++) {
if (ok(mid)) {
l = mid;
mid = (l + r) / 2;
} else {
r = mid;
mid = (l + r) / 2;
}
}

printf("%.12lf\n", l);

return 0;
}
```

#### Submission Info

Submission Time 2012-05-27 21:22:52+0900 C - 暗闇帰り道 kawatea C (GCC 4.4.7) 0 4916 Byte RE 1238 ms 13820 KB

#### Compile Error

```./Main.c:125: warning: built-in function ‘y1’ declared as non-function
./Main.c: In function ‘main’:
./Main.c:217: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result
./Main.c:219: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result
```

#### Judge Result

Set Name all
Score / Max Score 0 / 100
Status
 AC × 58 RE × 6
Set Name Test Cases
all 00_mini_01.txt, 00_mini_02.txt, 00_mini_03.txt, 00_mini_04.txt, 00_mini_05.txt, 00_sample_01.txt, 00_sample_02.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt, 01_rnd_20.txt, 02_maxrnd_01.txt, 02_maxrnd_02.txt, 02_maxrnd_03.txt, 02_maxrnd_04.txt, 02_maxrnd_05.txt, 02_maxrnd_06.txt, 02_maxrnd_07.txt, 02_maxrnd_08.txt, 02_maxrnd_09.txt, 02_maxrnd_10.txt, 02_maxrnd_11.txt, 02_maxrnd_12.txt, 02_maxrnd_13.txt, 02_maxrnd_14.txt, 02_maxrnd_15.txt, 02_maxrnd_16.txt, 02_maxrnd_17.txt, 02_maxrnd_18.txt, 02_maxrnd_19.txt, 03_hard_01.txt, 03_hard_02.txt, 03_hard_03.txt, 03_hard_04.txt, 03_hard_05.txt, 03_hard_06.txt, 03_hard_07.txt, 03_hard_08.txt, 04_open_01.txt, 04_open_02.txt, 05_minihard_01.txt, 05_minihard_02.txt, 05_minihard_03.txt, 05_minihard_04.txt, 05_minihard_05.txt, 05_minihard_06.txt, 05_minihard_07.txt, 05_minihard_08.txt
Case Name Status Exec Time Memory
00_mini_01.txt AC 21 ms 684 KB
00_mini_02.txt AC 20 ms 664 KB
00_mini_03.txt AC 19 ms 664 KB
00_mini_04.txt AC 20 ms 684 KB
00_mini_05.txt AC 21 ms 692 KB
00_sample_01.txt AC 19 ms 660 KB
00_sample_02.txt AC 19 ms 660 KB
01_rnd_01.txt AC 1131 ms 9212 KB
01_rnd_02.txt AC 169 ms 3708 KB
01_rnd_03.txt AC 33 ms 1172 KB
01_rnd_04.txt AC 98 ms 1780 KB
01_rnd_05.txt AC 30 ms 1168 KB
01_rnd_06.txt AC 24 ms 944 KB
01_rnd_07.txt AC 38 ms 2196 KB
01_rnd_08.txt AC 237 ms 3720 KB
01_rnd_09.txt AC 329 ms 4980 KB
01_rnd_10.txt AC 444 ms 4864 KB
01_rnd_11.txt AC 226 ms 2544 KB
01_rnd_12.txt AC 144 ms 2052 KB
01_rnd_13.txt AC 50 ms 916 KB
01_rnd_14.txt AC 555 ms 3068 KB
01_rnd_15.txt AC 254 ms 2676 KB
01_rnd_16.txt AC 24 ms 1556 KB
01_rnd_17.txt AC 26 ms 2232 KB
01_rnd_18.txt AC 19 ms 888 KB
01_rnd_19.txt AC 22 ms 1944 KB
01_rnd_20.txt AC 22 ms 1812 KB
02_maxrnd_01.txt AC 331 ms 8444 KB
02_maxrnd_02.txt AC 247 ms 8572 KB
02_maxrnd_03.txt AC 382 ms 10488 KB
02_maxrnd_04.txt AC 657 ms 4472 KB
02_maxrnd_05.txt AC 380 ms 10112 KB
02_maxrnd_06.txt AC 1238 ms 5748 KB
02_maxrnd_07.txt AC 141 ms 6012 KB
02_maxrnd_08.txt AC 93 ms 7176 KB
02_maxrnd_09.txt AC 1231 ms 8292 KB
02_maxrnd_10.txt AC 197 ms 4084 KB
02_maxrnd_11.txt AC 1050 ms 4856 KB
02_maxrnd_12.txt AC 498 ms 5624 KB
02_maxrnd_13.txt AC 656 ms 6012 KB
02_maxrnd_14.txt AC 744 ms 6016 KB
02_maxrnd_15.txt AC 152 ms 5116 KB
02_maxrnd_16.txt AC 553 ms 4468 KB
02_maxrnd_17.txt AC 421 ms 4216 KB
02_maxrnd_18.txt AC 41 ms 3844 KB
02_maxrnd_19.txt AC 40 ms 3828 KB
03_hard_01.txt RE 1147 ms 13812 KB
03_hard_02.txt RE 281 ms 13808 KB
03_hard_03.txt AC 71 ms 9716 KB
03_hard_04.txt AC 79 ms 9720 KB
03_hard_05.txt RE 296 ms 13808 KB
03_hard_06.txt RE 287 ms 13820 KB
03_hard_07.txt AC 73 ms 9720 KB
03_hard_08.txt AC 80 ms 9720 KB
04_open_01.txt RE 301 ms 13820 KB
04_open_02.txt RE 293 ms 13816 KB
05_minihard_01.txt AC 24 ms 780 KB
05_minihard_02.txt AC 23 ms 764 KB
05_minihard_03.txt AC 21 ms 788 KB
05_minihard_04.txt AC 22 ms 788 KB
05_minihard_05.txt AC 21 ms 788 KB
05_minihard_06.txt AC 24 ms 784 KB
05_minihard_07.txt AC 21 ms 784 KB
05_minihard_08.txt AC 22 ms 736 KB