Cod sursa(job #1253684)

Utilizator danalex97Dan H Alexandru danalex97 Data 1 noiembrie 2014 17:33:06
Problema Car Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.63 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;

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

const int N = 510;

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

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

int n,m,x,y,sx,sy,a[N][N],dp[N][N][8];

struct tup
{
    int x,y,d;
};

tup make_tup(int x,int y,int z)
{
    tup out;
    out.x = x , out.y = y , out.d = z;
    return out;
}

vector<tup> v[2];
int cost,now,infi;

bool good(int x,int y)
{
    if ( x < 1 || y < 1 || x > n || y > m ) return 0;
    if ( a[x][y] == 1 ) return 0;
    return 1;
}

bool arrive(int x,int y)
{
    for (int d=0;d<8;++d)
        if ( dp[x][y][d] < infi )
            return 1;
    return 0;
}

int main()
{
    F>>n>>m;
    F>>x>>y>>sx>>sy;
    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j)
            F>>a[i][j];
    memset(dp,0x3f,sizeof(dp));
    infi = dp[0][0][0];
    for (int d=0;d<8;++d)
    {
        dp[x][y][d] = 0;
        v[0].push_back( make_tup(x,y,d) );
    }
    now = 0;
    while ( !v[now].empty() )
    {
        //for (int d=0;d<8;++d,G<<'\n') for (int i=1;i<=n;++i,G<<'\n') for (int j=1;j<=m;++j) if (dp[i][j][d]==infi) G<<"! "; else G<<dp[i][j][d]<<' '; G<<"---------------\n";
        for (int i=0;i<int(v[now].size());++i)
        {
            tup x = v[now][i];
            if ( dp[x.x+dx[x.d]][x.y+dy[x.d]][x.d] == infi && good(x.x+dx[x.d],x.y+dy[x.d]) )
            {
                dp[x.x+dx[x.d]][x.y+dy[x.d]][x.d] = dp[x.x][x.y][x.d];
                v[now].push_back( make_tup(x.x+dx[x.d],x.y+dy[x.d],x.d) );
            }
            if ( dp[x.x][x.y][(x.d+1)%8] == infi )
            {
                dp[x.x][x.y][(x.d+1)%8] = dp[x.x][x.y][x.d] + 1;
                v[(now+1)%2].push_back( make_tup(x.x,x.y,(x.d+1)%8) );
            }
            if ( dp[x.x][x.y][(x.d-1+8)%8] != infi && dp[x.x][x.y][x.d] + 1 < dp[x.x][x.y][(x.d-1+8)%8] )
                dp[x.x][x.y][(x.d-1+8)%8] = dp[x.x][x.y][x.d] + 1;
            if ( dp[x.x][x.y][(x.d-1+8)%8] == infi )
            {
                dp[x.x][x.y][(x.d-1+8)%8] = dp[x.x][x.y][x.d] + 1;
                v[(now+1)%2].push_back( make_tup(x.x,x.y,(x.d-1+8)%8) );
            }
        }
        v[now].clear();
        now = (now+1) % 2;
        ++cost;
    }
    G<<"-1\n";
    return 0;
    int ans = infi;
    for (int d=0;d<8;++d)
        ans = min(ans,dp[sx][sy][d]);
    if (ans == infi )
        G<<"-1\n";
    else
        G<<ans<<'\n';
}