Submission #885534

#	Time	Username	Problem	Language	Result	Execution time	Memory
885534		huutuan	Maze (JOI23_ho_t3)	C++14	100 / 100	530 ms	340948 KiB

Main

#include<bits/stdc++.h>

using namespace std;

// #define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define isz(x) ((int)(x).size())
#define sumof(x) accumulate(all(x), 0ll)

const int dx[]={1, -1, 0, 0, 1, 1, -1, -1}, dy[]={0, 0, 1, -1, 0, 1, -1, 1, -1};
int n, r, c;
int sr, sc, gr, gc;

template<class T>
struct Vec{
   int size;
   T data[6000001];
   void clear(){
      size=0;
   }
   void push_back(const T &x){
      data[size++]=x;
   }
   auto & operator[](int x){
      return data[x];
   }
   const auto & operator[](int x) const {
      return data[x];
   }
};

template<class T>
struct Queue{
   int bq, eq;
   T data[6000001];
   int size() const {
      return eq-bq+1;
   }
   void clear(){
      bq=1; eq=0;
   }
   T & front(){
      return data[bq];
   }
   void push(const T &x){
      data[++eq]=x;
   }
   void pop(){
      ++bq;
   }
};

void solve(){
   cin >> r >> c >> n;
   cin >> sr >> sc >> gr >> gc;
   vector<vector<char>> a(r+1, vector<char>(c+1));
   vector<vector<int>> dist(r+1, vector<int>(c+1, 1e9));
   vector<vector<pair<int, int>>> dist2(r+1, vector<pair<int, int>>(c+1));
   for (int i=1; i<=r; ++i) for (int j=1; j<=c; ++j) cin >> a[i][j];
   Vec<pair<int, int>> roots;
   roots.push_back({sr, sc});
   Queue<pair<int, int>> q;
   auto bfs_white=[&](int distance){
      q.clear();
      for (int i=0; i<roots.size; ++i) q.push({roots[i].first, roots[i].second}), dist[roots[i].first][roots[i].second]=distance;
      roots.clear();
      while (q.size()){
         int u=q.front().first, v=q.front().second;
         q.pop();
         for (int i=0; i<4; ++i){
            int x=u+dx[i], y=v+dy[i];
            if (x<1 || y<1 || x>r || y>c || dist[x][y]<1e9) continue;
            if (a[x][y]=='.'){
               dist[x][y]=distance;
               q.push({x, y});
            }else{
               roots.push_back({x, y}), dist[x][y]=distance+1;
            }
         }
      }
   };
   Queue<pair<int, int>> qq;
   auto bfs_black=[&](int distance){
      qq.clear();
      for (int i=0; i<roots.size; ++i) qq.push(roots[i]);
      roots.clear();
      while (qq.size()){
         int u=qq.front().first, v=qq.front().second;
         roots.push_back({u, v});
         qq.pop();
         for (int i=0; i<4; ++i){
            int x=u+dx[i], y=v+dy[i];
            if (x<1 || y<1 || x>r || y>c || dist[x][y]<1e9) continue;
            int d2x=dist2[u][v].first, d2y=dist2[u][v].second;
            d2x+=!!dx[i], d2y+=!!dy[i];
            if (d2x>=n || d2y>=n) continue;
            dist[x][y]=distance;
            dist2[x][y]={d2x, d2y};
            qq.push({x, y});
         }
      }
   };
   int cur=0;
   while (dist[gr][gc]>=1e9){
      bfs_white(cur);
      bfs_black(++cur);
   }
   cout << dist[gr][gc];
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   int ntests=1;
   // cin >> ntests;
   for (int i=1; i<=ntests; ++i) solve();
   return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:23:11: warning: 'roots.Vec<std::pair<int, int> >::size' may be used uninitialized in this function [-Wmaybe-uninitialized]
   23 |       data[size++]=x;
      |       ~~~~^
Main.cpp:61:24: note: 'roots.Vec<std::pair<int, int> >::size' was declared here
   61 |    Vec<pair<int, int>> roots;
      |                        ^~~~~

• 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