Submission #916525

#	Time	Username	Problem	Language	Result	Execution time	Memory
916525		Darren0724	Maze (JOI23_ho_t3)	C++17	8 / 100	306 ms	84108 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define all(x) x.begin(),x.end()
#define abcorz ios_base::sync_with_stdio(false);cin.tie(0);
const int INF=1e18;
int32_t main(){
    abcorz;
    int n,m,k;cin>>n>>m>>k;
    vector<vector<int>> v(n+2,vector<int>(m+2,1));
    vector<vector<int>> dis(n+2,vector<int>(m+2,INF));
    int s1,s2;cin>>s1>>s2;
    int t1,t2;cin>>t1>>t2;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char c;cin>>c;
            v[i][j]=(c=='#');
        }
    }
    vector<int> dx={-1,1,0,0},dy={0,0,-1,1};
    priority_queue<pair<int,pair<int,int>>> pq;
    dis[s1][s2]=0;
    pq.push({0,{s1,s2}});
    while(pq.size()){
        auto[d,tmp]=pq.top();
        pq.pop();
        d=-d;
        auto [s1,s2]=tmp;
        if(d!=dis[s1][s2]){
            continue;
        }
        for(int k=0;k<4;k++){
            int t1=s1+dx[k];
            int t2=s2+dy[k];
            if(t1==0||t1==n+1||t2==0||t2==m+1){
                continue;
            }
            if(dis[t1][t2]>dis[s1][s2]+v[s1][s2]+v[t1][t2]){
                dis[t1][t2]=dis[s1][s2]+v[s1][s2]+v[t1][t2];
                pq.push({-dis[t1][t2],{t1,t2}});
            }
        }
    }
    
    cout<<dis[t1][t2]/2<<endl;
    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 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