Suntuubi-palvelussa käytetään evästeitä. Palvelua käyttämällä hyväksyt evästeiden käytön. Lue lisää. OK

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

#define max_size 3000
#define max_size2 3002

// Datatähti 2009 - Task 2
//
// Shortest path solution with O(n,m) = n*m
//
// Note: Optimized (complicated) solution due to relatively strict speed requirements
//
// Source by Gorath
//
int main() {
    int m, n, i, y, x, yn, xn, r, fs=0, fe=0, bs=0, be=0, moves[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
    short int (*route)[max_size], (*free)[3], (*bush)[3];
    char (*map)[max_size2];

    FILE *fin, *fout;
    fin = fopen("pensas.in","r");
    fout = fopen("pensas.out","w");

    // Varaa muistia muutujille ~= 9M * 7 * 2 bytes + 9M * 1 bytes = 135M
    free = malloc(sizeof(short int)*max_size*max_size*3);
    bush = malloc(sizeof(short int)*max_size*max_size*3);
    route = malloc(sizeof(short int)*max_size*max_size);
    map = malloc(sizeof(char)*max_size*max_size2);
    memset(route,-1,sizeof(short int)*max_size*max_size);

    // Lue tiedot
    fscanf(fin,"%d %d\n",&m,&n);
    for (y=0;y<m;y++) fgets(map[y],max_size2,fin);

    // Algoritmi
    y=x=r=route[0][0]=0;
    for (;;) {
        for (i=0;i<4;i++) {
            yn = y + moves[i][0];
            xn = x + moves[i][1];
            if (yn<0 || yn>=m || xn<0 || xn>=n || route[yn][xn]!=-1) continue;
            route[yn][xn] = i;
            if (map[yn][xn]=='V') {
                free[fe][0] = yn;
                free[fe][1] = xn;
                free[fe][2] = r;
                fe++;
            } else {
                bush[be][0] = yn;
                bush[be][1] = xn;
                bush[be][2] = r + 1;
                be++;
            }
        }

        if (fs!=fe) {
            y = free[fs][0];
            x = free[fs][1];
            r = free[fs][2];
            fs++;
        } else if (bs!=be) {
            y = bush[bs][0];
            x = bush[bs][1];
            r = bush[bs][2];
            bs++;
        }

        if (y==m-1 && x==n-1) break;
    }

    // Kirjoita vastaus ja sulje tiedostot
    fprintf(fout,"%d\n",r);
    while (y!=0 || x!=0) {
        i = route[y][x];
        y = y - moves[i][0];
        x = x - moves[i][1];
        if (map[y][x]=='P') fprintf(fout,"%d %d\n",y+1,x+1);
    }
    fclose(fin);
    fclose(fout);

    return 0;
}


©2019 layout9 - suntuubi.com