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

Submission #19472

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 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;

if (ok(0) == 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:33:05+0900 C - 暗闇帰り道 kawatea C (GCC 4.4.7) 100 4219 Byte AC 1497 ms 4348 KB

#### Compile Error

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

#### Judge Result

Set Name all
Score / Max Score 100 / 100
Status
 AC × 64
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 58 ms 664 KB
00_mini_02.txt AC 24 ms 664 KB
00_mini_03.txt AC 22 ms 660 KB
00_mini_04.txt AC 22 ms 668 KB
00_mini_05.txt AC 24 ms 692 KB
00_sample_01.txt AC 22 ms 660 KB
00_sample_02.txt AC 22 ms 656 KB
01_rnd_01.txt AC 1160 ms 3432 KB
01_rnd_02.txt AC 162 ms 2440 KB
01_rnd_03.txt AC 33 ms 1028 KB
01_rnd_04.txt AC 98 ms 1536 KB
01_rnd_05.txt AC 36 ms 912 KB
01_rnd_06.txt AC 22 ms 908 KB
01_rnd_07.txt AC 34 ms 1928 KB
01_rnd_08.txt AC 218 ms 2940 KB
01_rnd_09.txt AC 330 ms 3068 KB
01_rnd_10.txt AC 437 ms 3012 KB
01_rnd_11.txt AC 227 ms 2060 KB
01_rnd_12.txt AC 144 ms 1788 KB
01_rnd_13.txt AC 50 ms 1032 KB
01_rnd_14.txt AC 562 ms 2684 KB
01_rnd_15.txt AC 247 ms 2156 KB
01_rnd_16.txt AC 25 ms 1536 KB
01_rnd_17.txt AC 33 ms 2052 KB
01_rnd_18.txt AC 25 ms 984 KB
01_rnd_19.txt AC 25 ms 2008 KB
01_rnd_20.txt AC 24 ms 1872 KB
02_maxrnd_01.txt AC 339 ms 3968 KB
02_maxrnd_02.txt AC 246 ms 4348 KB
02_maxrnd_03.txt AC 370 ms 3968 KB
02_maxrnd_04.txt AC 633 ms 4348 KB
02_maxrnd_05.txt AC 372 ms 4088 KB
02_maxrnd_06.txt AC 1249 ms 4096 KB
02_maxrnd_07.txt AC 132 ms 3976 KB
02_maxrnd_08.txt AC 84 ms 3968 KB
02_maxrnd_09.txt AC 1209 ms 3964 KB
02_maxrnd_10.txt AC 194 ms 3964 KB
02_maxrnd_11.txt AC 1055 ms 3968 KB
02_maxrnd_12.txt AC 496 ms 3924 KB
02_maxrnd_13.txt AC 648 ms 4192 KB
02_maxrnd_14.txt AC 754 ms 3972 KB
02_maxrnd_15.txt AC 145 ms 3972 KB
02_maxrnd_16.txt AC 549 ms 3964 KB
02_maxrnd_17.txt AC 410 ms 3840 KB
02_maxrnd_18.txt AC 42 ms 3924 KB
02_maxrnd_19.txt AC 41 ms 3848 KB
03_hard_01.txt AC 1331 ms 4060 KB
03_hard_02.txt AC 1386 ms 3916 KB
03_hard_03.txt AC 76 ms 3840 KB
03_hard_04.txt AC 80 ms 3844 KB
03_hard_05.txt AC 1338 ms 3948 KB
03_hard_06.txt AC 1415 ms 3920 KB
03_hard_07.txt AC 74 ms 3832 KB
03_hard_08.txt AC 80 ms 3836 KB
04_open_01.txt AC 1497 ms 3848 KB
04_open_02.txt AC 1426 ms 3840 KB
05_minihard_01.txt AC 24 ms 784 KB
05_minihard_02.txt AC 27 ms 848 KB
05_minihard_03.txt AC 23 ms 776 KB
05_minihard_04.txt AC 24 ms 780 KB
05_minihard_05.txt AC 25 ms 860 KB
05_minihard_06.txt AC 25 ms 732 KB
05_minihard_07.txt AC 23 ms 784 KB
05_minihard_08.txt AC 24 ms 780 KB