Submission #988314

#	Time	Username	Problem	Language	Result	Execution time	Memory
988314		Otalp	Maze (JOI23_ho_t3)	C++14	100 / 100	1357 ms	346776 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second


vector<vector<int> > a;
vector<vector<int> > dp, us;
vector<vector<int> > e;

void solve(){
    int h, w, n;
    cin>>h>>w>>n;
    for(int i=0; i<=h + 1; i++){
        dp.pb({});
        a.pb({});
        us.pb({});
        e.pb({});
        for(int j=0; j<=w + 1; j++){
            dp[i].pb(0);
            a[i].pb(0);
            us[i].pb(0);
            e[i].pb(0);
        }
    }
    pii s, f;
    cin>>s.ff>>s.ss;
    cin>>f.ff>>f.ss;
    for(int i=1; i<=h; i++){
        for(int j=1; j<=w; j++){
            char c;
            cin>>c;
            if(c == '#') a[i][j] = 1;
            else a[i][j] = 0;
        }
    }

    deque<pair<pii, int >> q, dq;
    dq.pb({s, n - 1});
    vector<pii> nap1={{0, 1}, {1, 0}, {0, -1}, {-1, 0}}, nap2 = {{1, -1}, {-1, 1}, {1, 1}, {-1, -1}};
    int ls = 0;
    while(dq.size()){
        q = dq;
        dq.clear();
        while(q.size()){
            int x = q[0].ff.ff, y = q[0].ff.ss;
            if(us[x][y]){
                q.pop_front();
                continue;
            }
            dp[x][y] = ls;
            us[x][y] = 1;
            e[x][y] = q[0].ss;
            //cout<<x<<' '<<y<<' '<<ls<<' '<<e[x][y]<<'\n';
            q.pop_front();
            for(pii H: nap1){
                int l=x + H.ff, r = y +H.ss;
                if(l <= 0 or l > h or r <= 0 or r > w) continue;
                if(e[x][y] == n - 1){
                    if(a[l][r] == 1){
                        dq.pb({{l, r}, 0});
                    }
                    else{
                        q.pb({{l, r}, e[x][y]});
                    }
                } 
                else{
                    q.pb({{l, r}, e[x][y] + 1});
                }
            }
            if(e[x][y] < n - 1){
                for(pii H: nap2){
                    int l=x + H.ff, r = y +H.ss;
                    if(l <= 0 or l > h or r <= 0 or r > w) continue;
                    q.pb({{l, r}, e[x][y] + 1});
                }
            }
        }
        ls ++;
    }
    cout<<dp[f.ff][f.ss];
}



int main(){
    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