Submission #19360

---

Source Code Expand

#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

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