Submission #1022542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022542		Aiperiii	Maze (JOI23_ho_t3)	C++14	62 / 100	262 ms	60584 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 <int> > a(r+1,vector <int> (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++){
            char x;
            cin>>x;
            if(x=='#')a[i][j]=1;
        }
    }
    
    vector <int> X={0,0,1,-1};
    vector <int> Y={1,-1,0,0};
    queue <vector <int> > q2;
    queue <vector <int> > q;
    d[sx][sy]=0;
    q.push({sx,sy});
    
    while(!q.empty() or !q2.empty()){
        
        while(!q.empty()){
            int x=q.front()[0];
            int y=q.front()[1];
         
            q.pop();
            for(int i=0;i<4;i++){
                int x2=x+X[i],y2=y+Y[i];
                if(x2>=1 && x2<=r && y2>=1 && y2<=c){
                    if(a[x2][y2]==0 && d[x2][y2]>d[x][y]){
                        d[x2][y2]=d[x][y];
                        q.push({x2,y2});
                    }
                    if(a[x2][y2]==1 && d[x2][y2]>d[x][y]+1){
                        d[x2][y2]=d[x][y]+1;
                        q2.push({x2,y2,1,1});
                    }
                }
            }
        }
        
        while(!q2.empty()){
            int x=q2.front()[0];
            int y=q2.front()[1];
            int psx=q2.front()[2];
            int psy=q2.front()[3];
            if(psx==n or psy==n){
                q.push({x,y});
            }
            q2.pop();
            for(int i=0;i<4;i++){
                int x2=x+X[i],y2=y+Y[i];
                if(x2>=1 && x2<=r && y2>=1 && y2<=c){
                    int npsy=psy+abs(Y[i]);
                    int npsx=psx+abs(X[i]);
                    if(npsx<=n && npsy<=n){
                        if(d[x2][y2]>d[x][y]){
                            d[x2][y2]=d[x][y];
                            q2.push({x2,y2,npsx,npsy});
                        }
                    }
                }
            }
        }
    }
    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