Cod sursa(job #1041590)

Utilizator ericptsStavarache Petru Eric ericpts Data 25 noiembrie 2013 22:29:55
Problema Car Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.58 kb
#include <fstream>
#include <queue>
#include <utility>
#include <cstring>

using namespace std;

const int MAX_N = 505;

const int dx[] = {0,0, 1,1, 1,-1,-1,-1};
const int dy[] = {1,-1,1,0,-1, 1, 0,-1};


int bst[MAX_N][MAX_N][8];
int all[MAX_N][MAX_N];
bool bad[MAX_N][MAX_N];

struct state{
    int x,y;
    int from;
};

queue<state> Q;

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

int n,m;
int x0,y0;
int x1,y1;
int cost[100];

bool shift45(int orig, int nxt){
    return dx[orig] - dy[orig] == dx[nxt] &&
           dx[orig] + dy[orig] == dy[nxt];
}

bool shift90(int orig, int nxt){
    return -dy[orig] == dx[nxt] &&
           dx[orig] == dy[nxt];
}

int get_deg(int orig, int nxt){

    if(orig == nxt)
        return 0;
    if(shift45(orig, nxt) || shift45(nxt, orig))
        return 45;
    if(shift90(orig, nxt) || shift90(nxt, orig))
        return 90;

    return -1;
}

void spread(){

    state now;
    now.x = x0;
    now.y = y0;

    memset(bst, 0x3f, sizeof(bst));
    memset(all, 0x3f, sizeof(all));

    int i,j;
    for(int i = 0 ; i < 8 ; ++i) {
        now.from = i;
        bst[x0][y0][i] = 0;
        Q.push(now);
    }

    while(!Q.empty()){
        now = Q.front();
        Q.pop();

        for(int i = 0 ; i < 8 ; ++i){
            const int next_x = now.x + dx[i],
                      next_y = now.y + dy[i];
            int deg = get_deg(now.from, i);

            if(deg == -1)
                continue;


            if(next_x < 1 || next_x > n || next_y < 1 || next_y > m)
                continue;

            if(bad[next_x][next_y])
                continue;

            if(all[next_x][next_y] + 2 < bst[now.x][now.y][now.from] + cost[deg]
               || bst[next_x][next_y][i] < bst[now.x][now.y][now.from] + cost[deg])
                continue;

            bst[next_x][next_y][i] = bst[now.x][now.y][now.from] + cost[deg];

            Q.push((state){next_x,next_y,i});

            if(bst[next_x][next_y][i] < all[next_x][next_y])
                all[next_x][next_y] = bst[next_x][next_y][i];
        }
    }
}

int main(){
    cost[0] = 0;
    cost[45] = 1;
    cost[90] = 2;

    in >> n >> m;

    in >> x0 >> y0;

    in >> x1 >> y1;

    for(int i = 1 ; i <= n ; ++i)for(int j = 1 ; j <= m ; ++j)
        in >> bad[i][j];

    spread();

    int ans = -1;

    for(int i = 0 ; i < 8 ; ++i)
        if(ans == -1 || bst[x1][y1][i] < ans)
            ans = bst[x1][y1][i];

    if(ans == 0x3f3f3f3f)
        ans = -1;

    out << ans << "\n";
    return 0;
}