제출 #1346569

#제출 시각아이디문제언어결과실행 시간메모리
1346569cpismayilmmdv985Toy (CEOI24_toy)C++20
100 / 100
215 ms288280 KiB
#ifdef LOCAL
#include ".debug.hpp"
#else
#define debug(...) 42
#endif
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;

const int MXN = 2000;
char grid[MXN][MXN];
int N, M, K, L, targetX = 0, targetY = 0, XH, YH, XV, YV;
vector<int> block_row[MXN], block_col[MXN]; 
bool vis[MXN][MXN];

inline bool free(const int &x, const int &y) {
   return x >= 0 && y >= 0 && x < N && y < M && grid[x][y] != 'X';
}

array<int, 2> getrange(const int &type, const int &x, const int &y) {
   if (!free(x, y))  return {0, -1};
   if (!type) {
      // horizontal line
      auto it = upper_bound(block_row[x].begin(), block_row[x].end(), y);  
      int rwall = *it - 1, lwall = *(--it) + 1;
      return {lwall, rwall};
   }
   // vertical line
   auto it = upper_bound(block_col[y].begin(), block_col[y].end(), x);
   int bwall = *it - 1, uwall = *(--it) + 1;
   return {uwall, bwall};
}

int caloverlap(const array<int, 2> &point1, const array<int, 2> &point2) {
   int l = max(point1[0], point2[0]), r = min(point1[1], point2[1]);
   return max(0, r - l + 1);
}

void dfs(const int &x, const int &y) {
   if (vis[x][y]) return;
   vis[x][y] = true;
   if (x == targetX && y == targetY) {
      cout << "YES\n";
      exit(0);
   }
   array<int, 2> currh = getrange(0, x, y), currv = getrange(1, x, y);
   array<int, 2> nexth = getrange(0, x + 1, y),  prevh = getrange(0, x - 1, y);
   array<int, 2> rightv = getrange(1, x, y + 1), leftv = getrange(1, x, y - 1);
   if (caloverlap(currh, nexth) >= K)
      if (x + 1 <= currv[1])  dfs(x + 1, y);
   if (caloverlap(currh, prevh) >= K)
      if (x - 1 >= currv[0])  dfs(x - 1, y);
   if (caloverlap(currv, leftv) >= L)
      if (y - 1 >= currh[0])  dfs(x, y - 1);
   if (caloverlap(currv, rightv) >= L)
      if (y + 1 <= currh[1])  dfs(x, y + 1);
}

signed main() {
#ifndef VOID
   cin.tie(nullptr)->sync_with_stdio(false);
#endif

   cin >> M >> N >> K >> L >> XH >> YH >> XV >> YV;
   swap(XH, YH), swap(XV, YV);
   for (int i = 0; i < N; i++)   block_row[i].push_back(-1);
   for (int j = 0; j < M; j++)   block_col[j].push_back(-1);
   for (int i = 0; i < N; i++)
      for (int j = 0; j < M; j++) {
         cin >> grid[i][j];
         if (grid[i][j] == '*') targetX = i, targetY = j;
         if (grid[i][j] == 'X')  block_row[i].push_back(j), block_col[j].push_back(i);
      }
   for (int i = 0; i < N; i++)   block_row[i].push_back(M);
   for (int j = 0; j < M; j++)   block_col[j].push_back(N);
   dfs(XH, YV);
   cout << "NO\n";

   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...