Submission #1069243

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069243		epicci23	Maze (JOI23_ho_t3)	C++17	100 / 100	1479 ms	1174556 KiB

Main

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

int n,m,k,a,b,c,d;
vector<vector<int>> v,dist,vis,pot;
const int INF = 1e9;

bool is_valid(int x,int y){
  return (x>=1 && x<=n && y>=1 && y<=m && !v[x][y] && !vis[x][y]);
}

bool _Valid(int x,int y){
  return (x>=1 && x<=n && y>=1 && y<=m && !vis[x][y]);
}

vector<array<int,2>> Extend(queue<array<int,2>> q){
  vector<array<int,2>> New;
  while(!q.empty()){
  	int A=q.front()[0],B=q.front()[1];
  	q.pop();
    for(int dx=-1;dx<=1;dx++)
      for(int dy=-1;dy<=1;dy++)
      	if(is_valid(A+dx,B+dy) && abs(dx)+abs(dy)==1){
      	  q.push({A+dx,B+dy});
      	  New.push_back({A+dx,B+dy});
      	  vis[A+dx][B+dy]=1;
      	  dist[A+dx][B+dy]=dist[A][B];
      	}
  }
  return New;
}


vector<array<int,2>> Update(queue<array<int,2>> q){
  vector<array<int,2>> New;
  while(!q.empty()){
  	int A=q.front()[0],B=q.front()[1];
  	q.pop();
    for(int dx=-1;dx<=1;dx++)
      for(int dy=-1;dy<=1;dy++){
      	if(!_Valid(A+dx,B+dy)) continue;
      	if(pot[A][B]==k) continue;
      	if(pot[A][B]==0 && abs(dx)+abs(dy)==1){
      	  q.push({A+dx,B+dy});
      	  New.push_back({A+dx,B+dy});
      	  vis[A+dx][B+dy]=1;
      	  dist[A+dx][B+dy]=dist[A][B]+1;
      	  pot[A+dx][B+dy]=pot[A][B]+1;
      	}
      	if(pot[A][B]>0){
      	  q.push({A+dx,B+dy});
      	  New.push_back({A+dx,B+dy});
      	  vis[A+dx][B+dy]=1;
      	  dist[A+dx][B+dy]=dist[A][B];
      	  pot[A+dx][B+dy]=pot[A][B]+1;
      	}
      }
  }
  return New;
}
void _(){
  cin >> n >> m >> k;
  cin >> a >> b >> c >> d;
  dist.assign(n+5,vector<int>(m+5,INF));
  v.assign(n+5,vector<int>(m+5,0));
  pot.assign(n+5,vector<int>(m+5,0));
  vis.assign(n+5,vector<int>(m+5,0));
  for(int i=1;i<=n;i++){
  	string s;cin >> s;
  	for(int j=1;j<=m;j++){
  	  if(s[j-1]=='.') v[i][j]=0;
  	  else v[i][j]=1;
  	}
  }
  pot[a][b]=dist[a][b]=0;
  vis[a][b]=1;
  queue<array<int,2>> q;
  q.push({a,b});
  while(dist[c][d]==INF){
  	vector<array<int,2>> round;
  	queue<array<int,2>> qq=q;
    vector<array<int,2>> cur=Extend(qq);
    for(array<int,2> x:cur){
      round.push_back(x);
      q.push(x);
    }
    qq=q;
    vector<array<int,2>> Swarm=Update(qq);
    for(array<int,2> x:Swarm) round.push_back(x);
    for(array<int,2> x:round) pot[x[0]][x[1]]=0;
    while(!q.empty()) q.pop();
    for(array<int,2> x:round) q.push(x);
  }
  cout << dist[c][d] << '\n';
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

• 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