Cod sursa(job #969062)

Utilizator CosminRusuCosmin Rusu CosminRusu Data 3 iulie 2013 13:57:19
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <ctime>
#include <utility>
#include <string.h>

using namespace std;

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

const int MAXN = 505,
            oo = ((1<<31)-1),
            dx[8]={ 1, 1, 0, -1, -1, -1,  0,  1 },
            dy[8]={ 0, 1, 1,  1,  0, -1, -1, -1 };

struct mpair{
    int x, y, dir;
    mpair(int _x, int _y, int _dir){
        x = _x;
        y = _y ;
        dir = _dir;
    }
};

queue <mpair> Q[2];
int a[MAXN][MAXN], d[MAXN][MAXN][8];
int n, m;

inline bool isokay(int i, int j)
{
    return (i >= 1 && j >= 1 && i <= n && j <= m && !a[i][j]);
}

int main()
{
    int stx, sty, fnx, fny;
    cin >> n >> m;
    cin >> stx >> sty >> fnx >> fny;
    for(int i = 1 ; i <= n ; ++ i)
        for(int j = 1 ; j <= m ; ++ j)
        {
            cin >> a[i][j];
            for(int k = 0 ; k < 8 ; ++ k)
                d[i][j][k] = oo;
        }
    cin.close();
    for(int i = 0 ; i < 8 ; ++ i)
    {
        d[stx][sty][i] = 0;
        Q[0].push(mpair(stx, sty, i));
    }
    int c = 0 ;
    while(true)
    {
        int i;
        for(i = 0 ; Q[i].empty() ; ++i);
        if(i >= 2)
            break;
        int x = Q[i].front().x;
        int y = Q[i].front().y;
        int dir = Q[i].front().dir;
        Q[i].pop();
        // "tot inainte"
        int xnou = x + dx[dir];
        int ynou = y + dy[dir];
        if( isokay(xnou, ynou) && d[xnou][ynou][dir] > d[x][y][dir])
        {
            d[xnou][ynou][dir] = d[x][y][dir];
            Q[0].push(mpair(xnou, ynou, dir));
        }
        if( d[x][y][(dir+8+1)&7] > d[x][y][dir] + 1)
        {
            d[x][y][(dir+8+1)&7] = d[x][y][dir] + 1;
            Q[1].push(mpair(x, y, (dir+8+1)&7));
        }
        if( d[x][y][(dir+8-1)&7] > d[x][y][dir] + 1)
        {
            d[x][y][(dir+8-1)&7] = d[x][y][dir] + 1;
            Q[1].push(mpair(x, y, (dir+8-1)&7));
        }
    }
    int sol = oo;
    for(int i = 0 ; i < 8 ; ++ i)
        sol = min(sol, d[fnx][fny][i]);
    cout << ( sol == oo ? -1 : sol) << "\n";
    cout.close();
    return 0;
}