Cod sursa(job #2451020)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 25 august 2019 13:35:25
Problema Car Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.54 kb
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream in("car.in");
ofstream out("car.out");
const int maxn = 505;
int dp[maxn][maxn][10];
int M[maxn][maxn];
int n, m;

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

struct muchie
{
    int x, y;
    int dir, cost;
};

queue <muchie> q1;
queue <muchie> q2;

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

int main()
{
    pair <int, int> p1;
    pair <int, int> p2;
    in >> n >> m >> p1.first >> p1.second >> p2.first >> p2.second;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            in >> M[i][j];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            for(int dir = 0; dir < 8; dir++)
                dp[i][j][dir] = (1 << 30);
    for(int dir = 0; dir < 8; dir++)
        q1.push({p1.first, p1.second, dir, 0});

    while(!q1.empty())
    {
        while(!q1.empty())
        {
            muchie p = q1.front();
            q1.pop();
            muchie nou = {p.x + dx[p.dir], p.y + dy[p.dir], p.dir, p.cost};
            if(inside(nou.x, nou.y) && dp[nou.x][nou.y][nou.dir] > nou.cost)
            {
                dp[nou.x][nou.y][nou.dir] = nou.cost;
                q1.push(nou);
            }
            nou.x = p.x;
            nou.y = p.y;
            nou.cost++;
            nou.dir = (nou.dir + 1) % 8;
            if(inside(nou.x, nou.y) && dp[nou.x][nou.y][nou.dir] > nou.cost)
            {
                dp[nou.x][nou.y][nou.dir] = nou.cost;
                q2.push(nou);
            }
            nou.dir = p.dir - 1;
            if(nou.dir < 0)
                nou.dir = 7;
            if(inside(nou.x, nou.y) && dp[nou.x][nou.y][nou.dir] > nou.cost)
            {
                dp[nou.x][nou.y][nou.dir] = nou.cost;
                q2.push(nou);
            }
        }
        while(!q2.empty())
        {
            muchie p = q2.front();
            q2.pop();
            q1.push(p);
        }
    }
    int mn = (1 << 30);
    for(int dir = 0; dir < 8; dir++)
        mn = min(mn, dp[p2.first][p2.second][dir]);
    /*
    for(int i = 1; i <= n; i++, cerr << "\n")
        for(int j = 1; j <= m; j++, cerr << "\n")
            for(int dir = 0; dir < 8; dir++)
                cerr << dp[i][j][dir] << " ";
    */
    if(mn == (1 << 30))
        out << -1;
    else
        out << mn;
    out << "\n";
    return 0;
}