제출 #884888

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
884888		huutuan	Maze (JOI23_ho_t3)	C++14	0 / 100	2087 ms	600 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, 0}, dy[]={0, 0, 1, -1, 0};
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];
   auto bfs_white=[&](vector<pair<int, int>> roots, int distance) -> vector<pair<int, int>> {
      queue<pair<int, int>> q;
      vector<pair<int, int>> found;
      for (auto &i:roots){
         int u=i.first, v=i.second;
         for (int j=0; j<5; ++j) for (int k=1; k<=n; ++k){
            int x=u+dx[j]*k, y=v+dy[j]*k;
            if (x<1 || y<1 || x>r || y>c || dist[x][y]<1e9 || a[x][y]=='#') continue;
            dist[x][y]=distance;
            q.emplace(x, y);
         }
      }
      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]=='.'){
               q.emplace(x, y);
               dist[x][y]=distance;
            }else{
               dist[x][y]=distance+1;
               found.emplace_back(x, y);
            }
         }
      }
      return found;
   };
   auto bfs_black=[&](vector<pair<int, int>> roots, int distance) -> vector<pair<int, int>> {
      vector<pair<int, int>> found=roots;
      for (auto &i:roots){
         int u=i.first, v=i.second;
         for (int j=0; j<4; ++j) for (int k=1; k<n; ++k){
            int x=u+dx[j]*k, y=v+dy[j]*k;
            if (x<1 || y<1 || x>r || y>c || dist[x][y]<1e9 || a[x][y]=='.') continue;
            dist[x][y]=distance;
            found.emplace_back(x, y);
         }
      }
      return found;
   };
   int cur=0;
   vector<pair<int, int>> roots{{sr, sc}};
   while (dist[gr][gc]>=1e9){
      bfs_white(roots, cur).swap(roots);
      bfs_black(roots, ++cur).swap(roots);
   }
   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;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 19
• Subtask 3: 0 / 16
• Subtask 4: 0 / 19
• Subtask 5: 0 / 5
• Subtask 6: 0 / 19
• Subtask 7: 0 / 8
• Subtask 8: 0 / 6