Submission #885438

#TimeUsernameProblemLanguageResultExecution timeMemory
885438huutuanMaze (JOI23_ho_t3)C++14
86 / 100
2040 ms76192 KiB
#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;
 
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));
   for (int i=1; i<=r; ++i) for (int j=1; j<=c; ++j) cin >> a[i][j];
   vector<pair<int, int>> roots{{sr, sc}};
   auto bfs_white=[&](int distance){
      queue<pair<int, int>> q;
      for (auto &i:roots) q.emplace(i.first, i.second), dist[i.first][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.emplace(x, y);
            }else{
               roots.emplace_back(x, y);
            }
         }
      }
   };
   auto bfs_black=[&](int distance){
      queue<pair<pair<int, int>, int>> q;
      for (auto &i:roots) q.push({i, 0});
      roots.clear();
      while (q.size()){
         int u=q.front().first.first, v=q.front().first.second, d=q.front().second;
         q.pop();
         if (d==3) continue;
         if ((d&1)==0){
            for (int i=2; i<4; ++i){
               int x=u, y=v;
               for (int j=1; j<=n; ++j){
                  if (x<1 || y<1 || x>r || y>c) break;
                  if (dist[x][y]<=distance-1) continue;
                  if (dist[x][y]!=distance){
                     dist[x][y]=distance;
                     roots.emplace_back(x, y);
                     q.push({{x, y}, d|1});
                  }
                  x+=dx[i];
                  y+=dy[i];
               }
            }
         }
         if ((d&2)==0){
            for (int i=0; i<2; ++i){
               int x=u, y=v;
               for (int j=1; j<=n; ++j){
                  if (x<1 || y<1 || x>r || y>c) break;
                  if (dist[x][y]<=distance-1) continue;
                  if (dist[x][y]!=distance){
                     dist[x][y]=distance;
                     roots.emplace_back(x, y);
                     q.push({{x, y}, d|2});
                  }
                  x+=dx[i];
                  y+=dy[i];
               }
            }
         }
      }
   };
   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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...