Submission #64556386

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T, typename U>
using ordered_multiset = tree<pair<T, U>, null_type, less<pair<T, U>>, rb_tree_tag, tree_order_statistics_node_update>;

using ll = long long;

void solve()
{
    ll h, w;
    cin >> h >> w;

    vector<string> grid(h);

    for (ll i = 0; i < h; i++)
    {
        cin >> grid[i];
    }

    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    a--, b--, c--, d--;

    ll src = w * a + b, dest = w * c + d;

    vector<vector<vector<ll>>> dist(h * w, vector<vector<ll>>(4, vector<ll>(2, LLONG_MAX)));
    set<array<ll, 4>> q;

    for (ll i = 0; i < 4; i++)
    {
        dist[src][i][0] = 0;
        q.insert(array<ll, 4> {dist[src][i][0], i, 0, src});
    }

    vector<ll> dx = {-1, 0, 1, 0};
    vector<ll> dy = {0, 1, 0, -1};

    while (!q.empty())
    {
        auto node = *q.begin();
        ll dir = node[1], op = node[2], u = node[3];
        q.erase(q.begin());

        ll x = u / w, y = u % w;

        for (ll i = 0; i < 4; i++)
        {
            ll nx = x + dx[i];
            ll ny = y + dy[i];

            if (nx >= 0 && nx < h && ny >= 0 && ny < w)
            {
                ll v = w * nx + ny;
                ll ndir = i, nop = 0;

                if (op)
                {
                    if (dir != ndir)
                    {
                        if (grid[nx][ny] == '#')
                        {
                            nop = 1;
                        }
                    }
                }

                else
                {
                    if (grid[nx][ny] == '#')
                    {
                        nop = 1;
                    }
                }

                if (dist[u][dir][op] + nop < dist[v][ndir][nop])
                {
                    q.erase(array<ll, 4>{dist[v][ndir][nop], ndir, nop, v});
                    dist[v][ndir][nop] = dist[u][dir][op] + nop;
                    q.insert(array<ll, 4>{dist[v][ndir][nop], ndir, nop, v});
                }
            }
        }
    }

    ll ans = LLONG_MAX;

    for (ll i = 0; i < 4; i++)
    {
        for (ll j = 0; j < 2; j++)
        {
            ans = min(ans, dist[dest][i][j]);
        }
    }

    cout << ans << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    ll t = 1;
    // cin >> t;

    while (t--)
    {
        solve();
    }

    return 0;
}

Submission Info

Judge Result