Cod sursa(job #865864)

Utilizator ELHoriaHoria Cretescu ELHoria Data 27 ianuarie 2013 10:48:00
Problema Car Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <fstream>
#include <queue>
#define pii pair<short,short>
#define x first
#define y second
#define mp make_pair
 
using namespace std;
   
ifstream cin("car.in");
ofstream cout("car.out");
                 
const int dx[] = {-1,-1,0,1,1,1,0,-1}, dy[] = {0,1,1,1,0,-1,-1,-1};
const int cc[] = {0,1,2,3,4,3,2,1};
const int NMAX = 512, inf = int(1e9);
int N, M;
bool isFree[NMAX][NMAX];
char inQ[NMAX][NMAX];
int cost[NMAX][NMAX][8];
pii S, D;
 
void readData() {
    cin>>N>>M;
    cin>>S.x>>S.y>>D.x>>D.y;
    for(int i = 1;i <= N;i++) {
        for(int j = 1;j <= M;j++) {
            cin>>isFree[i][j];
        }
    }
}
 
int bf() {
    for(int i = 1;i <= N;i++) {
        for(int j = 1;j <= M;j++) {
            for(int k = 0;k < 8;k++) {
                cost[i][j][k] = inf;   
            }
            isFree[i][j] ^= 1;
        }
    }
    queue< pair<pii,char> > q;
    if(isFree[S.x][S.y]) {
        for(int k = 0;k < 8;k++) {
            cost[S.x][S.y][k] = 0;
            inQ[S.x][S.y] |= (1<<k);
            q.push(mp(S,k));
        }
    }
    pii v, w;
    int dir;
    while(!q.empty()) {
        v = q.front().x;
        dir = q.front().y;
        inQ[v.x][v.y] ^= (1<<dir);
        q.pop();
        for(int k = 0;k < 8;k++) {
            int d = dir + k;
            d -= d < 8 ? 0 : 8;
            w = mp(v.x + dx[d],v.y + dy[d]);
            if(isFree[w.x][w.y]) {
                if(cost[w.x][w.y][d] > cost[v.x][v.y][dir] + cc[k]) {
                    cost[w.x][w.y][d] = cost[v.x][v.y][dir] + cc[k];
                    if(((inQ[w.x][w.y]>>d) & 1) == 0) {
                        inQ[w.x][w.y] |= (1<<d);
                        q.push(mp(w,d));
                    }
                }
            }
        }
    }
    int ans = inf;
    for(int k = 0;k < 8;k++) {
        ans = min(ans,cost[D.x][D.y][k]);
    }
    return ans == inf ? -1 : ans;
}
 
int main()
{
    readData();
    cout<<bf();
    return 0;
}