Cod sursa(job #1912929)

Utilizator Mircea_DonciuDonciu Mircea Mircea_Donciu Data 8 martie 2017 11:10:05
Problema Car Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <fstream>
#include <cstring>
using namespace std;
const int kInf=0x3f3f3f3f;
const int dx[]={0,1,1,1,0,-1,-1,-1},dy[]={-1,-1,0,1,1,1,0,-1};
int n,m,i,j,sx,sy,fx,fy,qs[3],dist[505][505][8];
char buffer[1005];
bool a[505][505];
struct Node
{
    int x, y, d;
}q[3][2505];
void SetDist(int x, int y, int d, int cost)
{
    int qi = cost % 3;
    q[qi][qs[qi]].x = x;
    q[qi][qs[qi]].y = y;
    q[qi][qs[qi]].d = d;
    ++qs[qi];
    dist[x][y][d] = cost;
}
int main()
{
    ifstream f("car.in");
    ofstream g("car.out");
    (f>>n>>m>>sx>>sy>>fx>>fy).ignore(1);
    for(i=1; i<=n; i++)
    {
        f.getline(buffer + 2, 1005);
        for (j=1; j<=m; j++)
        a[i][j] = (buffer[j << 1] == '0');
    }
    memset(dist, kInf, sizeof dist);
    for (int i = 0; i < 8; ++i)
        SetDist(sx, sy, i, 0);
    for (int cost=0; qs[0]+qs[1]+qs[2]; cost++)
    {
        int crt=cost%3;
        for (int i = 0; i<qs[crt]; i++)
        {
            int x = q[crt][i].x;
            int y = q[crt][i].y;
            int d = q[crt][i].d;
            if ((x==fx&&y==fy)||dist[x][y][d]!=cost)
            continue;
            for (int i = -2; i <= 2; ++i)
            {
                int nd =(d+i)&7;
                int nx =x+dx[nd];
                int ny =y+dy[nd];
                int ncost=cost+max(i,-i);
                if (a[nx][ny]&&ncost<dist[nx][ny][nd])
                SetDist(nx, ny, nd, ncost);
            }
        }
        qs[crt] = 0;
    }
    int ans=kInf;
    for (i=0; i<8; i++)
    ans=min(ans, dist[fx][fy][i]);
    g<<(ans==kInf ? -1 : ans)<< "\n";
    f.close(); g.close();
    return 0;
}