Submission #791905

#	Time	Username	Problem	Language	Result	Execution time	Memory
791905		cig32	Maze (JOI23_ho_t3)	C++17	43 / 100	1834 ms	879444 KiB

Main

#include "bits/stdc++.h"
using namespace std;
//#define int long long
const int MAXN = 1e7 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
  if(p==0) return 1 % MOD;
  int r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
int inv(int b) { 
  return bm(b, MOD-2);
}
int fastlog(int x) {
  return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }
int r,c,n,sr,sc,gr,gc;
vector<vector<char>>a;
vector<int>adj[MAXN];
int dist[MAXN];
bool vis[MAXN];
int nxt;
int f(int i, int j) {
  return i*c+j;
}
void solve(int tc) {
  for(int i=0; i<MAXN; i++) dist[i] = 1e9;
  cin>>r>>c>>n;
  cin>>sr>>sc;
  cin>>gr>>gc;
  sr--,sc--,gr--,gc--;
  a.resize(r);
  for(int i=0;i<r;i++){
    a[i].resize(c);
    for(int j=0;j<c;j++){
      cin>>a[i][j];
    }
  }
  for(int i=0;i<r;i++){
    for(int j=0;j+1<c;j++){
      if(a[i][j]=='.'&&a[i][j+1]=='.'){
        adj[f(i,j)].push_back(f(i,j+1));
        adj[f(i,j+1)].push_back(f(i,j));
      }
    }
  }
  for(int i=0;i+1<r;i++){
    for(int j=0;j<c;j++){
      if(a[i][j]=='.'&&a[i+1][j]=='.'){
        adj[f(i,j)].push_back(f(i+1,j));
        adj[f(i+1,j)].push_back(f(i,j));
      }
    }
  }
  //pt3
  for(int i=0;i<r;i++){
    for(int j=0;j<c;j++){
      if(i%n != n-1 && i+1 < r) {
        adj[f(2*r+i, j)].push_back(f(2*r+i+1, j));
        adj[f(6*r+i, j)].push_back(f(6*r+i+1, j));
      }
      if(j%n != n-1 && j+1 < c) {
        adj[f(2*r+i, j)].push_back(f(2*r+i, j+1));
        adj[f(6*r+i, j)].push_back(f(6*r+i, j+1));
      }
    }
  }
  for(int i=0;i<r;i++){
    for(int j=0;j<c;j++){
      if(i%n != n-1 && i+1 < r) {
        adj[f(3*r+i, j)].push_back(f(3*r+i+1, j));
        adj[f(7*r+i, j)].push_back(f(7*r+i+1, j));
      }
      if(j%n != 0 && j-1 >= 0) {
        adj[f(3*r+i, j)].push_back(f(3*r+i, j-1));
        adj[f(7*r+i, j)].push_back(f(7*r+i, j-1));
      }
    }
  }
  for(int i=0;i<r;i++){
    for(int j=0;j<c;j++){
      if(i%n != 0 && i-1 >= 0) {
        adj[f(4*r+i, j)].push_back(f(4*r+i-1, j));
        adj[f(8*r+i, j)].push_back(f(8*r+i-1, j));
      }
      if(j%n != 0 && j-1 >= 0) {
        adj[f(4*r+i, j)].push_back(f(4*r+i, j-1));
        adj[f(8*r+i, j)].push_back(f(8*r+i, j-1));
      }
    }
  }
  for(int i=0;i<r;i++){
    for(int j=0;j<c;j++){
      if(i%n != 0 && i-1 >= 0) {
        adj[f(5*r+i, j)].push_back(f(5*r+i-1, j));
        adj[f(9*r+i, j)].push_back(f(9*r+i-1, j));
      }
      if(j%n != n-1 && j+1 < c) {
        adj[f(5*r+i, j)].push_back(f(5*r+i, j+1));
        adj[f(9*r+i, j)].push_back(f(9*r+i, j+1));
      }
    }
  }
  for(int i=2;i<6;i++){
    for(int j=0;j<r*c;j++){
      adj[j].push_back(i*r*c+j);
    }
  }
  for(int i=6;i<10;i++){
    for(int j=0;j<r*c;j++){
      adj[i*r*c+j].push_back(j);
    }
  }
  for(int i=0;i+n-1<r;i++){
    for(int j=0;j+n-1<c;j++){
      adj[f(r+i,j)].push_back(f(6*r+i,j));
      adj[f(4*r+i,j)].push_back(f(r+i,j));
      if(j%n!=0) {
        adj[f(r+i,j)].push_back(f(7*r+i,j+n-1));
        adj[f(5*r+i,j+n-1)].push_back(f(r+i,j));
      }
      if(i%n!=0) {
        adj[f(r+i,j)].push_back(f(9*r+i+n-1,j));
        adj[f(3*r+i+n-1,j)].push_back(f(r+i,j));
      }
      if(i%n!=0 && j%n!=0) {
        adj[f(r+i,j)].push_back(f(8*r+i+n-1,j+n-1));
        adj[f(2*r+i+n-1,j+n-1)].push_back(f(r+i,j));
      }
    }
  }
  //pt2
  for(int i=0;i+n-1<r;i++){
    for(int j=0;j+n-1<c;j++){
      for(int k=-n+1;k<n;k+=n-1){
        if(i+k>=0 && i+k<r && j>=n) adj[f(r+i,j)].push_back(f(r+i+k,j-n));
        if(i+k>=0 && i+k<r && j+n<c) adj[f(r+i,j)].push_back(f(r+i+k,j+n));
        if(j+k>=0 && i>=n && j+k<c) adj[f(r+i,j)].push_back(f(r+i-n,j+k));
        if(j+k>=0 && i+n<r && j+k<c) adj[f(r+i,j)].push_back(f(r+i+n,j+k));
        if(k==n-1)break;
      }
    }
  }
  for(int i=0;i<r;i++){
    for(int j=0;j<c;j++){
      if(j%n!=n-1 && j+1<c) {
        adj[f(10*r+i,j)].push_back(f(10*r+i,j+1));
        adj[f(11*r+i,j+1)].push_back(f(11*r+i,j));
        adj[f(14*r+i,j)].push_back(f(14*r+i,j+1));
        adj[f(15*r+i,j+1)].push_back(f(15*r+i,j));
      }
      if(i%n!=n-1 && i+1<r){
        adj[f(12*r+i,j)].push_back(f(12*r+i+1,j));
        adj[f(13*r+i+1,j)].push_back(f(13*r+i,j));
        adj[f(16*r+i,j)].push_back(f(16*r+i+1,j));
        adj[f(17*r+i+1,j)].push_back(f(17*r+i,j));
      }
      if(a[i][j]=='.') {
        adj[f(14*r+i,j)].push_back(f(i,j));
        adj[f(15*r+i,j)].push_back(f(i,j));
        adj[f(16*r+i,j)].push_back(f(i,j));
        adj[f(17*r+i,j)].push_back(f(i,j));
        adj[f(i,j)].push_back(f(10*r+i,j));
        adj[f(i,j)].push_back(f(11*r+i,j));
        adj[f(i,j)].push_back(f(12*r+i,j));
        adj[f(i,j)].push_back(f(13*r+i,j));
      }
    }
  }
  for(int i=0;i+n-1<r;i++){
    for(int j=0;j+n-1<c;j++){
      if(j>0) {
        adj[f(r+i,j)].push_back(f(16*r+i,j-1));
        adj[f(r+i,j)].push_back(f(17*r+i+n-1,j-1));
        adj[f(12*r+i+n-1,j-1)].push_back(f(r+i,j));
        adj[f(13*r+i,j-1)].push_back(f(r+i,j));
      }
      if(j+n<c) {
        adj[f(r+i,j)].push_back(f(16*r+i,j+n));
        adj[f(r+i,j)].push_back(f(17*r+i+n-1,j+n));
        adj[f(12*r+i+n-1,j+n)].push_back(f(r+i,j));
        adj[f(13*r+i,j+n)].push_back(f(r+i,j));
      }
      if(i>0) {
        adj[f(r+i,j)].push_back(f(14*r+i-1,j));
        adj[f(r+i,j)].push_back(f(15*r+i-1,j+n-1));
        adj[f(10*r+i-1,j+n-1)].push_back(f(r+i,j));
        adj[f(11*r+i-1,j)].push_back(f(r+i,j));
      }
      if(i+n<r) {
        adj[f(r+i,j)].push_back(f(14*r+i+n,j));
        adj[f(r+i,j)].push_back(f(15*r+i+n,j+n-1));
        adj[f(10*r+i+n,j+n-1)].push_back(f(r+i,j));
        adj[f(11*r+i+n,j)].push_back(f(r+i,j));
      }
    }
  }
  
  queue<int> q[2];
  q[0].push(f(sr, sc));
  int tar = f(gr, gc);
  dist[f(sr, sc)]=0;
  //unordered_map<int, int> prv;
  while(q[0].size() || q[1].size()) {
    for(int i=0; i<2; i++) {
      if(q[i].size()) {
        int f = q[i].front(); q[i].pop();
        if(f == tar) {
          /*
          int bruh = f;
          stack<int>stk;
          while(bruh != sr*c+sc) {
            stk.push(bruh);
            bruh=prv[bruh];
          }
          stk.push(sr*c+sc);
          while(stk.size()){
            int x=stk.top();
            cout<<x/(r*c)<<' '<<(x%(r*c))/c<<' '<<(x%(r*c))%c<<'\n';
            stk.pop();
          }
          cout<<'\n';
          */
          cout << dist[f] << '\n'; return;
        }
        if(!vis[f]) {
          vis[f] = 1;
          for(int x: adj[f]) {
            if(!vis[x] && dist[x] > dist[f] + (x >= r*c && x < 2*r*c)) {
              dist[x] = dist[f] + (x >= r*c && x < 2*r*c);
             // prv[x] = f;
              if(x >= r*c && x < 2*r*c) q[1].push(x);
              else q[0].push(x);
            }
          }
        }
        break;
      }
    }
  }
  
  

}
int32_t main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}
// 勿忘初衷
/*
8 9 5
3 1
2 9
.#..###.#
##..#.##.
.###..#.#
#.....##.
..###....
#......##
.##.#.###
#.##.###.
*/

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