Cod sursa(job #881074)

Utilizator MagnvsDaniel Constantin Anghel Magnvs Data 17 februarie 2013 18:06:00
Problema Car Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <fstream>
#include <queue>

using namespace std;

ifstream fin("car.in");
ofstream fout("car.out");

const int nmax= 500, cmax= 5, dmax= 8;
const int dx[8]= {-1, -1, 0, 1, 1, 1, 0, -1}, 
    dy[8]= {0, 1, 1, 1, 0, -1, -1, -1};

int cst[dmax][dmax];
bool u[nmax+2][nmax+2][dmax];

struct coord{
    int x, y, d;
    coord(int x, int y, int d){
        this->x= x; this->y= y; this->d= d;
    }
};
queue <coord> q[cmax];

bool q_not_empty(){
    for (int i= 0; i<cmax; ++i){
        if (q[i].empty()==0){
            return 1;
        }
    }
    return 0;
}

int main(){
    for (int i= 0; i<dmax; ++i){
        for (int j= 0; j<dmax; ++j){
            if (j<i){
                cst[i][j]= cst[j][i];
            }else if (i+8-j<j-i){
                cst[i][j]= i+8-j;
            }else{
                cst[i][j]= j-i;
            }
        }
    }

    int n, m;
    fin>>n>>m;
    int src_x, src_y, dest_x, dest_y;
    fin>>src_x>>src_y>>dest_x>>dest_y;
    for (int i= 1; i<=n; ++i){
        for (int j= 1; j<=m; ++j){
            fin>>u[i][j][0];
            if (u[i][j][0]){
                for (int k= 1; k<dmax; ++k){
                    u[i][j][k]= 1;
                }
            }
        }
    }
    for (int i= 0; i<dmax; ++i){
        for (int j= 0; j<=n+1; ++j){
            u[j][0][i]= 1;
            u[j][m+1][i]= 1;
        }
        for (int j= 1; j<=m; ++j){
            u[0][j][i]= 1;
            u[n+1][j][i]= 1;
        }
    }

    for (int i= 0; i<dmax; ++i){
        q[0].push(coord(src_x, src_y, i));
    }
    for (int i= 0; q_not_empty()&& i<=10; ++i){
        int ind= i%cmax;
        while (q[ind].empty()==0){
            int x= q[ind].front().x, y= q[ind].front().y, d= q[ind].front().d;
            if (x==dest_x&& y==dest_y){
                fout<<i<<"\n";
                return 0;
            }
            
            q[ind].pop();
            if (u[x][y][d]==0){
                u[x][y][d]= 1;
                
                for (int j= 0; j<dmax; ++j){
                    if (u[x+dx[j]][y+dy[j]][j]==0){
                        q[(ind+cst[d][j])%5].push(coord(x+dx[j], y+dy[j], j));
                    }
                }
            }
        }
    }
    fout<<"-1\n";

    return 0;
}