Submission #1272517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272517		meisgood	Maze (JOI23_ho_t3)	C++20	51 / 100	2106 ms	859108 KiB

Main

#include <bits/stdc++.h>
using namespace std ;
string A[3003] ;
vector <vector<vector<pair<int,int>>>> dist ;
vector <vector<vector<bool>>> v ;
priority_queue <tuple<pair<int,int>,int,int,int>,vector<tuple<pair<int,int>,int,int,int>>,greater<tuple<pair<int,int>,int,int,int>>> q ;
void pushh(pair<int,int> dd,int x,int y,int z){
  if (dd<dist[x][y][z]) q.push({dd,x,y,z}),dist[x][y][z]=dd ;
}
int main(){
  int N,M,K,i,j ;
  cin >> N >> M >> K ;
  int s1,s2,g1,g2 ;
  cin >> s1 >> s2 >> g1 >> g2 ;
  for (i = 1 ; i <= N ; i ++) cin >> A[i],A[i]='0'+A[i] ;
  dist=vector<vector<vector<pair<int,int>>>>(N+3,vector<vector<pair<int,int>>>(M+3,vector<pair<int,int>>(3,{INT_MAX,INT_MAX}))) ;
  v=vector<vector<vector<bool>>>(N+3,vector<vector<bool>>(M+3,vector<bool>(3,0))) ;
  q.push({{0,0},s1,s2,0}) ;
  while (!q.empty()){
    auto [dd,x,y,z]=q.top() ;
    auto [d1,d2]=dd ;
    q.pop() ;
    if (dd>dist[x][y][z]) continue ;
    if (v[x][y][z]) continue ;
    dist[x][y][z]=dd ;
    v[x][y][z]=1 ;
    // cout << x << " " << y << " " << z << " " << d1 << " " << d2 << endl ;
    if (z==0){
      pushh({d1+1,0},x,y,2) ;
    }
    if (z==2){
      pushh({d1,N},x,y,1) ;
    }
    if (z==1){
      pushh({d1,2*N},x,y,0) ;
      pushh({d1+1,0},x,y,2) ;
    }
    if (z==2&&d2+1<=K-1){
      if (x+1<=N) pushh({d1,d2+1},x+1,y,z) ;
      if (x-1>=1) pushh({d1,d2+1},x-1,y,z) ;
    }
    if (z==2){
      if (x+1<=N) pushh({d1+1,0},x+1,y,z) ;
      if (x-1>=1) pushh({d1+1,0},x-1,y,z) ;
    }
    if (z==1&&d2+1-N<=K-1){
      if (y+1<=M) pushh({d1,d2+1},x,y+1,z) ;
      if (y-1>=1) pushh({d1,d2+1},x,y-1,z) ;
    }
    if (z==1){
      if (y+1<=M) pushh({d1+1,N},x,y+1,2) ;
      if (y-1>=1) pushh({d1+1,N},x,y-1,2) ;
    }
    if (x+1<=N&&A[x+1][y]=='.') pushh({d1,2*N},x+1,y,0) ;
    if (x-1>=1&&A[x-1][y]=='.') pushh({d1,2*N},x-1,y,0) ;
    if (y+1<=M&&A[x][y+1]=='.') pushh({d1,2*N},x,y+1,0) ;
    if (y-1>=1&&A[x][y-1]=='.') pushh({d1,2*N},x,y-1,0) ;
    if (x+1<=N&&A[x+1][y]!='.') pushh({d1+1,0},x+1,y,2) ;
    if (x-1>=1&&A[x-1][y]!='.') pushh({d1+1,0},x-1,y,2) ;
    if (y+1<=M&&A[x][y+1]!='.') pushh({d1+1,0},x,y+1,2) ;
    if (y-1>=1&&A[x][y-1]!='.') pushh({d1+1,0},x,y-1,2) ;
  }
  cout << dist[g1][g2][0].first << endl ;
  return 0 ;
}

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