Cod sursa(job #3298767)

Utilizator Carnu_EmilianCarnu Emilian Carnu_Emilian Data 1 iunie 2025 15:37:35
Problema Car Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fcin("car.in");
ofstream fcout("car.out");
typedef long long ll;

const int N = 1e6 + 5;
const int M = 505;
bool v[M][M], viz[M][M][8];
int n, m, d[M][M][8];
int di[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dj[] = {0, 1, 1, 1, 0, -1, -1, -1};
/**

7 0 1
6   2
5 4 3

*/
struct nod
{
    short i, j;
    char niv; /// = k
};
vector<nod> L[N];

int main()
{
    int i1, j1, i2, j2;
    fcin >> n >> m >> i1 >> j1 >> i2 >> j2;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            fcin >> v[i][j];
    for (int i = 0; i <= n + 1; i++)
        v[i][0] = v[i][m + 1] = 1;
    for (int j = 0; j <= m + 1; j++)
        v[0][j] = v[n + 1][j] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            for (int k = 0; k < 8; k++)
                d[i][j][k] = 1e9;
    for (int k = 0; k < 8; k++)
    {
        d[i1][j1][k] = 0;
        L[0].push_back({i1, j1, k});
    }
    for (int i = 0; i < N; i++)
        for (int j = 0; j < L[i].size(); j++)
        {
            nod e = L[i][j];
            if (!viz[e.i][e.j][e.niv])
            {
                viz[e.i][e.j][e.niv] = 1;
//                cout << e.i << ' ' << e.j << ' ' << (int) e.niv << endl;
                for (int k = 0; k < 8; k++)
                {
                    int ii, jj, c;
                    ii = e.i + di[k];
                    jj = e.j + dj[k];
                    c = d[e.i][e.j][e.niv] + min(abs(k - e.niv), 8 - abs(k - e.niv));
                    if (!v[ii][jj] && !viz[ii][jj][k] &&
                        c < d[ii][jj][k])
                    {
//                cout << e.i << ' ' << e.j << ' ' << (int) e.niv << ' '<<
//                ii << ' ' << jj << ' ' << k << ' ' << c << endl;
                        d[ii][jj][k] = c;
                        L[c].push_back({ii, jj, k});
                    }
                }
            }
        }
    int rasp = 1e9;
//    for (int k = 0; k < 8; k++)
//        cout << d[i2][j2][k] << ' ';
    for (int k = 0; k < 8; k++)
        rasp = min(rasp, d[i2][j2][k]);
    fcout << rasp;
    fcin.close();
    fcout.close();
    return 0;
}