Cod sursa(job #2415815)

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

using namespace std;

class inputReader {
    
private:
    
    FILE *inputFile;
    static const int SIZE = 1 << 12;
    char buffer[SIZE]; int cursor;
    
    inline void advance( void ) {
        if( ++cursor == SIZE ) {
            cursor = 0;
            fread( buffer, SIZE, 1, inputFile );
        } return;
    }
    
    inline char current( void ) {
        return buffer[cursor];
    }
    
public:
    
    inputReader( const char *fileName ) {
        inputFile = fopen( fileName, "r" ); cursor = 0;
        fread( buffer, SIZE, 1, inputFile );
    }
    
    inputReader &operator >>( int &value ) {
        value = 0;
        
        while( current() < '0' || current() > '9' )
            advance();
        
        while( current() >= '0' && current() <= '9' ) {
            value = value * 10 + ( current() - '0' );
            advance();
        }
        
        return *this;
    }
    
} in( "car.in" );
ofstream out("car.out");

int n, m, xi, yi, xf, yf;
int 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;
}