Submission #18949

---

Source Code Expand

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

#define A double
#define B int
#define C int

typedef struct {
    A first;
    B second;
    C third;
} tuple;

int cmp_first(A a, A b)
{
    if (a > b) {
        return 1;
    } else if (a == b) {
        return 0;
    } else {
        return -1;
    }
}

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

int cmp_third(C a, C b)
{
    return a - b;
}

int cmp_tuple(tuple a, tuple b)
{
    int x = cmp_first(a.first, b.first);
    
    if (x != 0) return x;
    
    x = cmp_second(a.second, b.second);
    
    if (x != 0) return x;
    
    return cmp_third(a.third, b.third);
}

tuple make_tuple(A first, B second, C third)
{
    tuple t;
    
    t.first = first;
    t.second = second;
    t.third = third;
    
    return t;
}

#define P tuple

typedef struct _priority_queue {
    P value;
    int size;
    struct _priority_queue *left;
    struct _priority_queue *right;
} priority_queue;

int cmp_queue(P a, P b)
{
    return cmp_tuple(a, b);
}

priority_queue *meld(priority_queue *a, priority_queue *b)
{
    priority_queue *tmp;
    
    if (a == NULL) return b;
    
    if (b == NULL) return a;
    
    if (cmp_queue(a->value, b->value) > 0) {
        tmp = a;
        a = b;
        b = tmp;
    }
    
    a->right = meld(a->right, b);
    
    tmp = a->left;
    a->left = a->right;
    a->right = tmp;
    
    return a;
}

priority_queue *push(priority_queue *a, P value)
{
    priority_queue *tmp = malloc(sizeof(priority_queue));
    int x;
    
    if (a == NULL) {
        x = 1;
    } else {
        x = a->size + 1;
    }
    
    tmp->value = value;
    tmp->left = NULL;
    tmp->right = NULL;
    
    tmp = meld(tmp, a);
    
    tmp->size = x;
    
    return tmp;
}

priority_queue *pop(priority_queue *a)
{
    priority_queue *tmp;
    int x = a->size - 1;
    
    tmp = meld(a->left, a->right);
    
    if (tmp != NULL) tmp->size = x;
    
    free(a);
    
    return tmp;
}

P top(priority_queue *a)
{
    return a->value;
}

int empty(priority_queue *a)
{
    if (a == NULL) {
        return 1;
    } else {
        return 0;
    }
}

void clear(priority_queue *a)
{
    if (a->left != NULL) clear(a->left);
    if (a->right != NULL) clear(a->right);
    
    free(a);
}

double maximum(double a, double b)
{
    if (a > b) {
        return a;
    } else {
        return b;
    }
}

int main()
{
    int n, m, i, j;
    char s[500][501];
    int f[500][500];
    double a[1001];
    priority_queue *q = NULL;
    
    scanf("%d %d", &n, &m);
    
    for (i = 0; i < n; i++) scanf("%s", s[i]);
    
    a[0] = 1;
    
    for (i = 1; i <= 1000; i++) a[i] = a[i - 1] * 0.99;
    
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            f[i][j] = 0;
        }
    }
    
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            if (s[i][j] == 's') {
                q = push(q, make_tuple(-100, i * 500 + j, 0));
                
                break;
            }
        }
    }
    
    while (!empty(q)) {
        tuple t = top(q);
        int x, y, z;
        double c;
        
        q = pop(q);
        
        c = t.first;
        x = t.second / 500;
        y = (t.second - x * 500) % m;
        z = t.third + 1;
        
        if (s[x][y] == 'g') {
            printf("%.12lf\n", -c);
            
            return 0;
        }
        
        if (f[x][y] == 1) continue;
        
        f[x][y] = 1;
        
        if (x > 0 && s[x - 1][y] != '#' && f[x - 1][y] == 0) {
            if (s[x - 1][y] == 'g') {
                q = push(q, make_tuple(c, (x - 1) * 500 + y, z));
            } else {
                q = push(q, make_tuple(maximum(c, -(s[x - 1][y] - '0') * a[z]), (x - 1) * 500 + y, z));
            }
        }
        
        if (x < n - 1 && s[x + 1][y] != '#' && f[x + 1][y] == 0) {
            if (s[x + 1][y] == 'g') {
                q = push(q, make_tuple(c, (x + 1) * 500 + y, z));
            } else {
                q = push(q, make_tuple(maximum(c, -(s[x + 1][y] - '0') * a[z]), (x + 1) * 500 + y, z));
            }
        }
        
        if (y > 0 && s[x][y - 1] != '#' && f[x][y - 1] == 0) {
            if (s[x][y - 1] == 'g') {
                q = push(q, make_tuple(c, x * 500 + y - 1, z));
            } else {
                q = push(q, make_tuple(maximum(c, -(s[x][y - 1] - '0') * a[z]), x * 500 + y - 1, z));
            }
        }
        
        if (y < m - 1 && s[x][y + 1] != '#' && f[x][y + 1] == 0) {
            if (s[x][y + 1] == 'g') {
                q = push(q, make_tuple(c, x * 500 + y + 1, z));
            } else {
                q = push(q, make_tuple(maximum(c, -(s[x][y + 1] - '0') * a[z]), x * 500 + y + 1, z));
            }
        }
    }
    
    puts("-1");
    
    return 0;
}

Submission Info

Compile Error

./Main.c: In function ‘main’:
./Main.c:171: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result
./Main.c:173: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result

Judge Result