Cod sursa(job #2676120)

Utilizator ptudortudor P ptudor Data 23 noiembrie 2020 16:12:17
Problema Car Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.99 kb
#include<bits/stdc++.h>
#define fore(start,i,end) for(int i = start; i <= end; i++)
#define dbg(x)  #x << "=" << x << " "
#define dbg2(x,y)  "{" << x << "," << y << "} "
#define dbg3(x,y,k) "{" << x << "," << y << "," << k << "} "
#define dbg4(x,y,k,j) "{" << x << "," << y << "," << k << " , " << j << "} "

#define ll long long
#define f1 first
#define f2 second
#define inf 1000000005
#define debug_st(st) if (true) {cout << #st << " : "; stack<int> s123; while (!s123.empty()) cout << s123.top() << " ", s123.pop(); cout << "\n";}
#define debug_a(a,n) cout << #a << " : "; for(int i = 1; i <= n; i++) cout << a[i] << " "; cout << "\n";
#define debug_m(a,n,m) cout << #a << " :\n"; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++) cout << a[i][j] << " "; cout << "\n"; }cout << "\n";
#define debug_v(v) cout << #v << " : "; for(auto k : v) cout << k << " "; cout << "\n";
#define debug_s(s) cout << #s << " : "; for (auto k : s) cout << k < " "; cout << "\n";
#define debug_s2(s) cout << #s << " : "; for(auto k : s) cout << dbg2((*k).first,(*k).second); cout << "\n";
#define nmax 505

using namespace std;

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

int n,m,sy,sx,fy,fx,a[nmax][nmax],dp[nmax][nmax][9];
int dy[8] = {-1 , -1 , 0 , 1 , 1 , 1 , 0 , -1 };
int dx[8] = { 0 ,  1 , 1 , 1 , 0 , -1 , -1 , -1};
struct wow
{
    int y,x,dir,val;
    bool operator <(const wow other) const
    {
        return val < other.val;
    }
};
priority_queue<wow> q;
int mod(int x)
{
    if (x > 0) return x;
    return -x;
}
int cost_turn(int a, int b)
{
   // cout << dbg(a) << dbg(b) << " ans = " << min(mod(a - b) , min(mod(a - b) , 8 - mod(a - b))) << "\n";
    return min(mod(a - b) , 8 - mod(a - b));
}
int main()
{int i,j,k;
    in >> n >> m >> sy >> sx >> fy >> fx;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            in >> a[i][j];

    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            for (k = 1; k <= 8; k++)
                dp[i][j][k] = inf;

    for (k = 1; k <= 8; k++) {
        dp[sy][sx][k] = 0;
        q.push({sy , sx , k , 0});
    }


    while (!q.empty())
    {
        wow nod = q.top();
        q.pop();
        if (nod.val > dp[nod.y][nod.x][nod.dir])
            continue;

       // cout << dbg(nod.y) << dbg(nod.x) << dbg(nod.dir) << dbg(nod.val) << "\n";
        for (k = 1; k <= 8; k++)
        {
            int i = nod.y + dy[k - 1];
            int j = nod.x + dx[k - 1];

            if (a[i][j] == 1) continue;

            int newcost = dp[nod.y][nod.x][nod.dir] + cost_turn(nod.dir , k);

            if (dp[i][j][k] > newcost)
            {
                dp[i][j][k] = newcost;
                q.push({i , j , k , newcost});
            }
        }
    }
    int sol = inf;
    for (k = 1; k <= 8; k++)
        sol = min(dp[fy][fx][k] , sol);
    if (sol == inf)
        out << "-1\n";
    else
        out << sol << "\n";
}
///dir: 1 = sus, apoi mergi in sensul acelor de ceas