Submission #914140

#	Time	Username	Problem	Language	Result	Execution time	Memory
914140		mychecksedad	Maze (JOI23_ho_t3)	C++17	100 / 100	939 ms	246488 KiB

Main

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 6e6+100, M = 5000+10, K = 52, MX = 30;
 
int r, c, n, sx, sy, ex, ey, arr[4][2]={{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; 
string s[M];
vector<vector<int>> dp;
queue<array<int, 2>> Q[M];
void solve(){
  cin >> r >> c >> n >> sx >> sy >> ex >> ey;
  sx--, sy--, ex--, ey--;
  for(int i = 0; i < r; ++i) cin >> s[i];
 
 
  vector<vector<pair<int, int>>> C;
  vector<vector<int>> vis(r, vector<int>(c));
  vector<vector<array<int, 2>>> dist(r, vector<array<int, 2>>(c));
  vector<vector<int>> dp(r, vector<int>(c, MOD));
  for(int i = 0; i < r; ++i){
    for(int j = 0; j < c; ++j){
      if(s[i][j] == '#' || vis[i][j]) continue;
      queue<pair<int, int>> q;
      q.push({i, j});
      vis[i][j] = C.size() + 1;
      C.pb({});
      while(!q.empty()){
        int x = q.front().first, y = q.front().second;
        q.pop();
        C.back().pb({x, y});
        for(int l = 0; l < 4; ++l){
          int x1 = x + arr[l][0], x2 = y + arr[l][1];
          if(x1 >= 0 && x2 >= 0 && x1 < r && x2 < c && s[x1][x2] != '#' && !vis[x1][x2]){
            q.push({x1, x2});
            vis[x1][x2] = C.size();
          }
        }
      }
    }
  }
  // auto comp = [&](const array<int, 2> &x, const array<int, 2> &y){
  //   return max(abs(dist[x[0]][x[1]][0]), abs(dist[x[0]][x[1]][1])) > max(abs(dist[y[0]][y[1]][0]), abs(dist[y[0]][y[1]][1]));
  // };
  // priority_queue<array<int, 2>, vector<array<int, 2>>, decltype(comp)> Q(comp);
  for(auto p: C[vis[sx][sy] - 1]){
    int x = 0, req = 4;
    for(int l = 0; l < 4; ++l){
      int a = arr[l][0] + p.first, b = arr[l][1] + p.second;
      if(a >= 0 && b >= 0 && a < r && b < c){
        if(vis[a][b] == vis[p.first][p.second]) ++x;
      }else --req;
    }
    dp[p.first][p.second] = 0;
    dist[p.first][p.second] = {0};
    if(x < req) Q[0].push({p.first, p.second});
  }
  int cur = 0;
  while(dp[ex][ey] == MOD){
    vector<pair<int, int>> Sn;
    
    for(int i = 0; i <= n; ++i) while(!Q[i].empty()){
      int x = Q[i].front()[0], y = Q[i].front()[1]; Q[i].pop();
      if(max(abs(dist[x][y][0]), abs(dist[x][y][1])) < i) continue;
      // cout << x << ' '<< y << ' ' << cur << ' ' << dist[x][y][0] << ' ' << dist[x][y][1] << endl;
 
      int curx = dist[x][y][0], cury = dist[x][y][1];
      for(int l = 0; l < 4; ++l){
        int a = x + arr[l][0], b = y + arr[l][1];
        if(a >= 0 && b >= 0 && a < r && b < c){
          if(max(abs(curx + arr[l][0]), abs(cury + arr[l][1])) > n || abs(curx + arr[l][0]) + abs(cury + arr[l][1]) == 2*n){
            if(dp[a][b] == MOD && vis[a][b] > 0){
              for(auto p: C[vis[a][b] - 1]){
                dp[p.first][p.second] = cur + 1;
                Sn.pb(p);
              }
            }
            continue;
          }
          if(dp[a][b] < MOD){
            if(max(abs(dist[a][b][0]), abs(dist[a][b][1])) > max(abs(curx + arr[l][0]), abs(cury + arr[l][1]))){
              dist[a][b] = {curx + arr[l][0], cury + arr[l][1]};
            }
          }else{
            dp[a][b] = cur + 1;
            dist[a][b] = {curx + arr[l][0], cury + arr[l][1]};
            Sn.pb({a, b});
            Q[max(abs(dist[x][y][0]), abs(dist[x][y][1]))].push({a, b});
          }
        }
      }
    }
 
    for(auto p: Sn){
      int x = 0, req = 4;
      for(int l = 0; l < 4; ++l){
        int a = arr[l][0] + p.first, b = arr[l][1] + p.second;
        if(a >= 0 && b >= 0 && a < r && b < c){
          if(dp[a][b] < MOD) ++x;
        }else --req;
      }
      if(x < req){
        Q[0].push({p.first, p.second});
        dist[p.first][p.second] = {0};
      }
    }
    ++cur;
  }
  // for(int i = 0; i < r; ++i){
  //   for(int j = 0 ;j < c; ++j) cout << dp[i][j] << ' ';
  //   en;
  // }
  cout << dp[ex][ey];
}
 
 
int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
    en;
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
} 

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:124:15: warning: unused variable 'aa' [-Wunused-variable]
  124 |   int tt = 1, aa;
      |               ^~

• 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