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
Task C - 暗闇帰り道
User kawatea
Language C (GCC 4.4.7)
Score 0
Code Size 4916 Byte
Status RE
Exec Time 1238 ms
Memory 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