Submission #1022531

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022531		Aiperiii	Maze (JOI23_ho_t3)	C++14	62 / 100	169 ms	38820 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
using namespace std;

signed main(){
    int r,c,n;
    cin>>r>>c>>n;
    int sx,sy,tx,ty;
    cin>>sx>>sy>>tx>>ty;
    vector <vector <char> > a(r+1,vector <char> (c+1));
    vector <vector <int> > d(r+1,vector <int> (c+1,1e18));
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin>>a[i][j];
        }
    }
    d[sx][sy]=0;
    queue <pair <int,int> > q1;
    queue < pair <pair <int,int>,pair <int,int> > > q2;
    vector <int> X={0,0,1,-1};
    vector <int> Y={1,-1,0,0};
    q1.push({sx,sy});
    
    while(!q1.empty() || !q2.empty()){
        while(!q1.empty()){
            int x=q1.front().ff;
            int y=q1.front().ss;
            q1.pop();
            for(int i=0;i<4;i++){
                if(x+X[i]>=1 && x+X[i]<=r && y+Y[i]>=1 && y+Y[i]<=c){
                    if(a[x+X[i]][y+Y[i]]=='.' && d[x+X[i]][y+Y[i]]>d[x][y]){
                        d[x+X[i]][y+Y[i]]=d[x][y];
                        q1.push({x+X[i],y+Y[i]});
                    }
                    else if(a[x+X[i]][y+Y[i]]=='#' && d[x+X[i]][y+Y[i]]>d[x][y]+1){
                        d[x+X[i]][y+Y[i]]=d[x][y]+1;
                        q2.push({{x+X[i],y+Y[i]},{0,0}});
                    }
                }
            }
        }
        
        while(!q2.empty()){
            int x=q2.front().ff.ff;
            int y=q2.front().ff.ss;
            int dfx=q2.front().ss.ff;
            int dfy=q2.front().ss.ss;
            q2.pop();
            if(dfx==n-1 or dfy==n-1)q1.push({x,y});
            
            for(int i=0;i<4;i++){
               
                if(x+X[i]>=1 && x+X[i]<=r && y+Y[i]>=1 && y+Y[i]<=c){
                    int dfxn=dfx+(X[i]!=0);
                    int dfyn=dfy+(Y[i]!=0);
                    
                    if(dfxn<n && dfyn<n){
                        if(d[x+X[i]][y+Y[i]]>d[x][y]){
                            d[x+X[i]][y+Y[i]]=d[x][y];
                            q2.push({{x+X[i],y+Y[i]},{dfxn,dfyn}});
                        }
                    }
                    
                }
            }
        }
    }
    cout<<d[tx][ty]<<"\n";
}

/*
 
 */

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