Cod sursa(job #1493874)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 29 septembrie 2015 23:48:03
Problema Car Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 2.52 kb
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define INF 0x3f3f3f3f
#define MAXN 500
#define MAXK (5*MAXN*MAXN+1)
#define MAXD (2*MAXN*MAXN)
#define NRDIR 8
#define BUF_SIZE 4096
int dl[NRDIR]=
{
    -1, -1, 0, 1, 1, 1, 0, -1
};
int dc[NRDIR]=
{
    0, 1, 1, 1, 0, -1, -1, -1
};
int k, pos=BUF_SIZE;
char q[MAXN+2][MAXN+2];
int d[MAXN+1][MAXN+1][NRDIR], u[3];
typedef struct{
    int x, y, r;
}mycreation;
mycreation e[3][MAXN*MAXN+1];
char buf[BUF_SIZE];
FILE *fin;
inline char nextch(){
    if(pos==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fin);
        pos=0;
    }
    return buf[pos++];
}
inline int myabs(int a){
    if(a<0){
        return -a;
    }
    return a;
}
inline void adauga(int a, int b, int c, int o){
    d[b][c][o]=a;
    a%=3;
    e[a][++u[a]].x=b;
    e[a][u[a]].y=c;
    e[a][u[a]].r=o;
}
int main(){
    int n, m, x1, y1, x2, y2, i, j, t, ans, x, y, r, a, b, p, cost;
    char ch;
    FILE *fout;
    fin=fopen("car.in", "r");
    fout=fopen("car.out", "w");
    fscanf(fin, "%d%d%d%d%d%d ", &n, &m, &x1, &y1, &x2, &y2);
    for(i=1; i<=n; i++){
        for(j=1; j<=m; j++){
            ch=nextch();
            while(!isdigit(ch)){
                ch=nextch();
            }
            q[i][j]=ch-'0';
        }
    }
    for(i=0; i<=n+1; i++){
        q[i][0]=q[i][m+1]=1;
    }
    for(i=0; i<=m+1; i++){
        q[0][i]=q[n+1][i]=1;
    }
    for(i=1; i<=n; i++){
        for(j=1; j<=m; j++){
            for(t=0; t<NRDIR; t++){
                d[i][j][t]=INF;
            }
        }
    }
    for(i=0; i<NRDIR; i++){
        adauga(0, x1, y1, i);
    }
    t=0;
    cost=0;
    while(u[0]+u[1]+u[2]>0){
        for(p=1; p<=u[t]; p++){
            x=e[t][p].x;
            y=e[t][p].y;
            r=e[t][p].r;
            if(d[x][y][r]==cost){
                for(j=r-2; j<=r+2; j++){
                    i=(j+8)&7;
                    a=x+dl[i];
                    b=y+dc[i];
                    if((q[a][b]==0)&&(d[a][b][i]>d[x][y][r]+myabs(r-j))){
                        adauga(d[x][y][r]+myabs(r-j), a, b, i);
                    }
                }
            }
        }
        cost++;
        u[t]=0;
        t++;
        if(t==3){
            t=0;
        }
    }
    ans=INF;
    for(i=0; i<NRDIR; i++){
        if(ans>d[x2][y2][i]){
            ans=d[x2][y2][i];
        }
    }
    if(ans==INF){
        ans=-1;
    }
    fprintf(fout, "%d\n", ans);
    fclose(fin);
    fclose(fout);
    return 0;
}