Cod sursa(job #2415810)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 26 aprilie 2019 15:25:43
Problema Car Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.68 kb
#include <fstream>
#include <deque>
#define DIM 502
#define INF 1e9

using namespace std;

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

int n, m, xi, yi, xf, yf;
bool mat[DIM][DIM];

int dp[DIM][DIM][10];
bool viz[DIM][DIM][10];

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

/*
 0 - dreapta
 1 - dreapta sus
 2 - sus
 3 - stanga sus
 4 - stanga
 5 - stanga jos
 6 - jos
 7 - dreapta jos
*/

struct stare{
    int x, y, dir;
};

deque<stare> q;

int cost[DIM][DIM] = {
    {0, 1, 2, 3, 4, 3, 2, 1},
    {1, 0, 1, 2, 3, 4, 3, 2},
    {2, 1, 0, 1, 2, 3, 4, 3},
    {3, 2, 1, 0, 1, 2, 3, 4},
    {4, 3, 2, 1, 0, 1, 2, 3},
    {3, 4, 3, 2, 1, 0, 1, 2},
    {2, 3, 4, 3, 2, 1, 0, 1},
    {1, 2, 3, 4, 3, 2, 1, 0}
};

bool check(int x, int y){
    return (x >= 1 && x <= n && y >= 1 && y <= m && mat[x][y] == 0);
}

int main(int argc, const char * argv[]) {
    
    in>>n>>m;
    in>>xi>>yi>>xf>>yf;
    
    for(int i = 1; i <= n; ++ i){
        for(int j = 1; j <= m; ++ j){
            in>>mat[i][j];
        }
    }
    
    for(int i = 1; i <= n; ++ i){
        for(int j = 1; j <= m; ++ j){
            for(int k = 0; k < 8; ++ k){
                if(i != xi || j != yi)
                    dp[i][j][k] = INF;
            }
        }
    }
    
    for(int i = 0; i < 8; ++ i){
        int xc = xi + dx[i];
        int yc = yi + dy[i];
        if(check(xc, yc)){
            q.push_back({xc, yc, i});
            dp[xc][yc][i] = 0;
        }
    }
    
    while(!q.empty()){
        int x = q.front().x;
        int y = q.front().y;
        int dir = q.front().dir;
        q.pop_front();
        viz[x][y][dir] = 0;
        for(int i = 0; i < 8; ++ i){
            int xc = x + dx[i];
            int yc = y + dy[i];
            if(check(xc, yc) && i != dir){
                if(dp[xc][yc][i] > dp[x][y][dir] + cost[dir][i]){
                    dp[xc][yc][i] = dp[x][y][dir] + cost[dir][i];
                    if(viz[xc][yc][i] == 0){
                        q.push_back({xc, yc, i});
                        viz[xc][yc][i] = true;
                    }
                }
            }
        }
        
        int xc = x + dx[dir];
        int yc = y + dy[dir];
        
        while(check(xc, yc) && dp[xc][yc][dir] > dp[x][y][dir]){
            dp[xc][yc][dir] = dp[x][y][dir];
            if(viz[xc][yc][dir] == 0){
                q.push_back({xc, yc, dir});
                viz[xc][yc][dir] = true;
            }
            xc += dx[dir];
            yc += dy[dir];
        }
    }
    
    int minim = INF;
    
    for(int i = 0; i < 8; ++ i){
        minim = min(minim, dp[xf][yf][i]);
    }
    
    if(minim == INF)
        out<<-1;
    else
        out<<minim;
    
    return 0;
}