Submission #1278359

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278359		dosts	Maze (JOI23_ho_t3)	C++20	100 / 100	548 ms	152232 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e18;

const int N = 1e5+1;

void solve() {
    int n,m,k;
    cin >> n >> m >> k;
    pii start,targ;
    cin >> start.ff >> start.ss;
    cin >> targ.ff >> targ.ss;
    start.ff--,start.ss--;
    targ.ff--,targ.ss--;
    vector<string> grid(n);
    for (auto& row : grid) cin >> row;
    queue<pii> q1;
    queue<pair<pii,pii>> q2;
    q1.push(start);
    vector<vi> dist(n,vi(m,inf));
    dist[start.ff][start.ss] = 0;
    vi dx = {1,0,-1,0},dy = {0,1,0,-1};

    auto cool = [&](int x,int y) -> bool {
        if (x >= n || x < 0) return 0;
        if (y >= m || y < 0) return 0;
        return 1;
    };
    while (!q1.empty()) {
        while (!q1.empty()) {
            auto [x,y] = q1.front();
            q1.pop();
            for (int i = 0;i<4;i++) {
                int gx = x+dx[i],gy = y+dy[i];
                if (!cool(gx,gy)) continue;
                if (dist[gx][gy] != inf) continue;
                if (grid[gx][gy] == '#') {
                    dist[gx][gy] = dist[x][y]+1;
                    q2.push({{gx,gy},{1,1}});
                }
                else {
                    dist[gx][gy] = dist[x][y];
                    q1.push({gx,gy});
                }
            }
        }

        while (!q2.empty()) {
            auto [cell,mv] = q2.front();
            q2.pop();
            auto [x,y] = cell;
            q1.push({x,y});
            auto [rx,ry] = mv;
            for (int i = 0;i<4;i++) {
                int gx = x+dx[i],gy = y+dy[i];
                int rrx = rx+abs(dx[i]),rry = ry+abs(dy[i]);
                if (!cool(gx,gy)) continue;
                if (dist[gx][gy] != inf) continue;
                if (rrx > k || rry > k) continue;
                dist[gx][gy] = dist[x][y];
                q2.push({{gx,gy},{rrx,rry}});
            }
        }
    }
    cout << dist[targ.ff][targ.ss] << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

• 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