Submission #924282

#	Time	Username	Problem	Language	Result	Execution time	Memory
924282		vjudge1	Maze (JOI23_ho_t3)	C++17	27 / 100	2091 ms	13568 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int R, C, N;

bool isBest(int d1, int d2, pair<int, int> p){
    int mn1 = min(d1, d2);
    int mx1 = max(d1, d2);
    int mn2 = min(p.first, p.second);
    int mx2 = max(p.first, p.second);
    if(!((mx1 <= N && mn1 < N) || (mx2 <= N && mn2 < N))) return false;
    if(mx1 == mx2) return mn1 < mn2;
    else return mx1 < mx2;
}

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

    cin >> R >> C >> N;
    int Sr, Sc, Gr, Gc; cin >> Sr >> Sc >> Gr >> Gc; Sr--; Sc--; Gr--; Gc--;
    vector<string> v(R);
    for(auto &i : v) cin >> i;
    vector<vector<int>> dist(R, vector<int>(C, 1e9));
    vector<vector<bool>> vis(R, vector<bool>(C, false));
    dist[Sr][Sc] = 0;
    priority_queue<tuple<int, int, int>> q; q.push({0, Sr, Sc});
    while(!q.empty()){
        int i = get<1>(q.top()); int j = get<2>(q.top()); q.pop();
        if(vis[i][j]) continue;
        vis[i][j] = true;
        // cout << "i " << i+1 << " j " << j+1 << " dist " << dist[i][j] << "\n";
        for(int ai = -1; ai <= 1; ai++){
            for(int aj = -1; aj <= 1; aj++){
                if(ai * aj != 0 || i + ai < 0 || i + ai >= R || j + aj < 0 || j + aj >= C) continue;
                int ni = i + ai; int nj = j + aj;
                if(v[ni][nj] == '.' && dist[ni][nj] > dist[i][j]){
                    dist[ni][nj] = dist[i][j];
                    q.push({-dist[ni][nj], ni, nj});
                }
            }
        }
        for(int ai = -N; ai <= N; ai++){
            for(int aj = -N; aj <= N; aj++){
                if(min(abs(ai), abs(aj)) == N) continue;
                if(i + ai < 0 || i + ai >= R || j + aj < 0 || j + aj >= C) continue;
                int ni = i + ai; int nj = j + aj;
                // cout << "ni " << ni+1 << " nj " << nj+1 << "\n";
                if(dist[ni][nj] > dist[i][j]+1){
                    dist[ni][nj] = dist[i][j]+1;
                    q.push({-dist[ni][nj], ni, nj});
                }
            }
        }
    }
    cout << dist[Gr][Gc] << "\n";
}

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