제출 #750283

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
750283		Kihihihi	Maze (JOI23_ho_t3)	C++17	100 / 100	783 ms	258664 KiB

Main

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>
#include <ctime>
#include <chrono>
#include <cstdio>
#include <random>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <deque>
#include <queue>
#include <bitset>
#include <list>
#include <fstream>
#include <functional>
#include <complex>
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

short skip_cin = 0;
const long long INF = 1e18, MOD = 1e9 + 7, MOD2 = 998244353, LOG = 25;
const long double EPS = 1e-9, PI = acos(-1);

void solve()
{
    long long n, m, k;
    long long sx, sy, fx, fy;
    cin >> n >> m >> k >> sx >> sy >> fx >> fy;
    sx--; sy--; fx--; fy--;
    vector<string> t(n);
    for (long long i = 0; i < n; i++)
    {
        cin >> t[i];
    }

    vector<vector<long long>> dist(n, vector<long long>(m, INF));
    dist[sx][sy] = 0;
    deque<pair<long long, long long>> q = { { sx, sy } };
    const long long dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };
    vector<vector<bool>> edge(n, vector<bool>(m));
    while (q.size())
    {
        deque<pair<long long, long long>> nq = q;
        while (q.size())
        {
            auto [x, y] = q.front();
            q.pop_front();
            for (long long _ = 0; _ < 4; _++)
            {
                long long xx = x + dx[_], yy = y + dy[_];
                if (xx < 0 || yy < 0 || xx >= n || yy >= m || t[xx][yy] == '#')
                {
                    continue;
                }

                if (dist[xx][yy] > dist[x][y])
                {
                    dist[xx][yy] = dist[x][y];
                    q.push_back({ xx, yy });
                    nq.push_back({ xx, yy });
                }
            }
        }

        long long nd = dist[nq.front().first][nq.front().second] + 1;
        deque<pair<long long, long long>> ud = nq;
        while (nq.size())
        {
            auto [x, y] = nq.front();
            nq.pop_front();
            for (long long i = 1; i < k + 1; i++)
            {
                long long yy = y + i;
                if (yy >= m || dist[x][yy] != INF)
                {
                    break;
                }

                dist[x][yy] = nd;
                if (i == k)
                {
                    edge[x][yy] = true;
                }
                q.push_back({ x, yy });
                ud.push_back({ x, yy });
            }
            for (long long i = 1; i < k + 1; i++)
            {
                long long yy = y - i;
                if (yy < 0 || dist[x][yy] != INF)
                {
                    break;
                }

                dist[x][yy] = nd;
                if (i == k)
                {
                    edge[x][yy] = true;
                }
                q.push_back({ x, yy });
                ud.push_back({ x, yy });
            }
        }

        while (ud.size())
        {
            auto [x, y] = ud.front();
            ud.pop_front();
            for (long long i = 1; i < k + 1 - edge[x][y]; i++)
            {
                long long xx = x + i;
                if (xx >= n || dist[xx][y] != INF)
                {
                    break;
                }

                dist[xx][y] = nd;
                q.push_back({ xx, y });
            }
            for (long long i = 1; i < k + 1 - edge[x][y]; i++)
            {
                long long xx = x - i;
                if (xx < 0 || dist[xx][y] != INF)
                {
                    break;
                }

                dist[xx][y] = nd;
                q.push_back({ xx, y });
            }
        }
    }
    cout << dist[fx][fy] << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    srand(time(NULL));

    int tst = 1;
    //cin >> tst;
    while (tst--)
    {
        solve();
    }

    return 0;
}

/*
<3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3
⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠤⠖⠚⢉⣩⣭⡭⠛⠓⠲⠦⣄⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⡴⠋⠁⠀⠀⠊⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠳⢦⡀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⡴⠃⢀⡴⢳⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣆⠀⠀⠀
⠀⠀⠀⠀⡾⠁⣠⠋⠀⠈⢧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢧⠀⠀
⠀⠀⠀⣸⠁⢰⠃⠀⠀⠀⠈⢣⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣇⠀
⠀⠀⠀⡇⠀⡾⡀⠀⠀⠀⠀⣀⣹⣆⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀
⠀⠀⢸⠃⢀⣇⡈⠀⠀⠀⠀⠀⠀⢀⡑⢄⡀⢀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇
⠀⠀⢸⠀⢻⡟⡻⢶⡆⠀⠀⠀⠀⡼⠟⡳⢿⣦⡑⢄⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇
⠀⠀⣸⠀⢸⠃⡇⢀⠇⠀⠀⠀⠀⠀⡼⠀⠀⠈⣿⡗⠂⠀⠀⠀⠀⠀⠀⠀⢸⠁
⠀⠀⡏⠀⣼⠀⢳⠊⠀⠀⠀⠀⠀⠀⠱⣀⣀⠔⣸⠁⠀⠀⠀⠀⠀⠀⠀⢠⡟⠀
⠀⠀⡇⢀⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⠀⡇⠀⠀⠀⠀⠀⠀⠀⠀⢸⠃⠀
⠀⢸⠃⠘⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠁⠀⠀⢀⠀⠀⠀⠀⠀⣾⠀⠀
⠀⣸⠀⠀⠹⡄⠀⠀⠈⠁⠀⠀⠀⠀⠀⠀⠀⡞⠀⠀⠀⠸⠀⠀⠀⠀⠀⡇⠀⠀
⠀⡏⠀⠀⠀⠙⣆⠀⠀⠀⠀⠀⠀⠀⢀⣠⢶⡇⠀⠀⢰⡀⠀⠀⠀⠀⠀⡇⠀⠀
⢰⠇⡄⠀⠀⠀⡿⢣⣀⣀⣀⡤⠴⡞⠉⠀⢸⠀⠀⠀⣿⡇⠀⠀⠀⠀⠀⣧⠀⠀
⣸⠀⡇⠀⠀⠀⠀⠀⠀⠉⠀⠀⠀⢹⠀⠀⢸⠀⠀⢀⣿⠇⠀⠀⠀⠁⠀⢸⠀⠀
⣿⠀⡇⠀⠀⠀⠀⠀⢀⡤⠤⠶⠶⠾⠤⠄⢸⠀⡀⠸⣿⣀⠀⠀⠀⠀⠀⠈⣇⠀
⡇⠀⡇⠀⠀⡀⠀⡴⠋⠀⠀⠀⠀⠀⠀⠀⠸⡌⣵⡀⢳⡇⠀⠀⠀⠀⠀⠀⢹⡀
⡇⠀⠇⠀⠀⡇⡸⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠮⢧⣀⣻⢂⠀⠀⠀⠀⠀⠀⢧
⣇⠀⢠⠀⠀⢳⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⡎⣆⠀⠀⠀⠀⠀⠘
⢻⠀⠈⠰⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠰⠘⢮⣧⡀⠀⠀⠀⠀
⠸⡆⠀⠀⠇⣾⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠆⠀⠀⠀⠀⠀⠀⠀⠙⠳⣄⡀⢢⡀
<3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3
*/

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 16 / 16
• Subtask 4: 19 / 19
• Subtask 5: 5 / 5
• Subtask 6: 19 / 19
• Subtask 7: 8 / 8
• Subtask 8: 6 / 6