Submission #1350592

#TimeUsernameProblemLanguageResultExecution timeMemory
1350592ayazToy (CEOI24_toy)C++20
100 / 100
119 ms84020 KiB
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

#define int long long
#define all(x) (x).begin(), (x).end()
#define isz(x) (int)x.size()
const int sz = 2000;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
char g[sz][sz];
bool used[sz][sz];
array<int, 4> nearest[sz][sz];

void run(int tc) {
  int n, m, k, l, xv, yv, xh, yh; 
  cin >> n >> m >> k >> l >> xh >> yh >> xv >> yv;
  xh++, yh++, xv++, yv++;
  array<int, 2> target, start{yh, xv}; // y, x
  memset(used, false, sizeof(used));
  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
      cin >> g[i][j];
      if (g[i][j] == '*') {
        target = {i, j};
      }
    }
  }
  for (int i = 1; i <= m; i++) {
    int last = 0;
    for (int j = 1; j <= n; j++) {
      if (g[i][j] == 'X') {
        last = j;
        continue;
      }
      nearest[i][j][0] = last;
    }
    last = n + 1;
    for (int j = n; j >= 1; j--) {
      if (g[i][j] == 'X') {
        last = j;
        continue;
      }
      nearest[i][j][1] = last;
    }
  }
  for (int j = 1; j <= n; j++) {
    int last = 0;
    for (int i = 1; i <= m; i++) {
      if (g[i][j] == 'X') {
        last = i;
        continue;
      }
      nearest[i][j][2] = last;
    }
    last = m + 1;
    for (int i = m; i >= 1; i--) {
      if (g[i][j] == 'X') {
        last = i;
        continue;
      }
      nearest[i][j][3] = last;
    }
  }
  used[start[0]][start[1]] = true;
  queue<array<int, 2>> q;
  q.push(start);
  debug(target);
  while (!q.empty()) {
    auto [y, x] = q.front();
    q.pop();
    debug(y, x);
    for (int i = 0; i < 4; i++) {
      int ny = dy[i] + y;
      int nx = dx[i] + x;
      if (g[ny][nx] == 'X' || ny < 1 || nx < 1 || ny > m || nx > n) continue;
      debug(ny, nx);
      if (i == 2 || i == 3) {
        int len = min(nearest[y][x][1], nearest[ny][nx][1]) - max(nearest[y][x][0], nearest[ny][nx][0]) - 1;
        debug(len, "2");
        if (len >= k && !used[ny][nx]) {
          used[ny][nx] = true;
          q.push({ny, nx});
        }
      } else {
        int len = min(nearest[y][x][3], nearest[ny][nx][3]) - max(nearest[y][x][2], nearest[ny][nx][2]) - 1;
        debug(len, "1");
        if (len >= l && !used[ny][nx]) {
          used[ny][nx] = true;
          q.push({ny, nx});
        }
      }
    }
  }  
  cout << (used[target[0]][target[1]] ? "YES" : "NO") << '\n';
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int t = 1; // cin >> t;
  for (int tc = 1; tc <= t; tc++) run(tc);
}
#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...