제출 #1350557

#제출 시각아이디문제언어결과실행 시간메모리
1350557ayazToy (CEOI24_toy)C++20
0 / 100
8 ms5700 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];
int pre_y[sz], pre_x[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
  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++) {
    for (int j = 1; j <= n; j++) {
      pre_x[i] = pre_x[i - 1] + (g[i][j] == 'X');
    }
  }
  for (int j = 1; j <= n; j++) {
    for (int i = 1; i <= m; i++) {
      pre_y[j] = pre_y[j - 1] + (g[i][j] == 'X');
    }
  }
  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
      if (g[i][j] == 'X') {
        nearest[i][j] = {i, i, j, j};
        continue;
      }
      auto it = upper_bound(pre_x + i, pre_x + 1 + m, pre_x[i]) - pre_x;
      nearest[i][j][0] = it;
      it = lower_bound(pre_x, pre_x + i, pre_x[i]) - pre_x;
      nearest[i][j][1] = it;
      it = lower_bound(pre_y, pre_y + j, pre_y[j]) - pre_y;
      nearest[i][j][2] = it;
      it = upper_bound(pre_y + j, pre_y + 1 + n, pre_y[j]) - pre_y;
      nearest[i][j][3] = it;
    }
  }
  used[start[0]][start[1]] = true;
  queue<array<int, 2>> q;
  q.push(start);
  while (!q.empty()) {
    auto [y, x] = q.front();
    if (q.front() == target) break;
    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') continue;
      if (i == 0 || i == 1) {
        int len = nearest[ny][nx][0] - nearest[ny][nx][1];
        debug(len, "2");
        if (len >= l && !used[ny][nx]) {
          used[ny][nx] = true;
          q.push({ny, nx});
        }
      } else {
        int len = nearest[ny][nx][3] - nearest[ny][nx][2];
        debug(len, "1");
        if (len >= k && !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...