제출 #1342827

#제출 시각아이디문제언어결과실행 시간메모리
1342827OmarAlimammadzadeToy (CEOI24_toy)C++20
100 / 100
157 ms75612 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1505, d_row[] = {1, -1, 0, 0}, d_col[] = {0, 0, 1, -1};
int f_row, f_col, n, m, w, h;
int col_1, row_1, col_2, row_2;
int U[N][N], D[N][N], L[N][N], R[N][N];
char g[N][N];
bool vis[N][N];

void bfs() {
  queue<pair<int, int>> q;
  q.push({row_1, col_2});
  vis[row_1][col_2] = true;
  while (q.size()) {
    auto [row, col] = q.front();
    q.pop();
    if (row == f_row and col == f_col) {
      return;
    }
    for (int i = 0; i < 4; i++) {
      int n_row = row + d_row[i], n_col = col + d_col[i];
      if (g[n_row][n_col] == 'X' or
          !(1 <= n_row and n_row <= n and 1 <= n_col and n_col <= m)) {
        continue;
      }
      if (i < 2) { // roww
        int l = max(L[row][col], L[n_row][n_col]);
        int r = min(R[row][col], R[n_row][n_col]);
        if (r - l - 1 >= w and !vis[n_row][n_col]) {
          q.push({n_row, n_col});
          vis[n_row][n_col] = true;
        }
      } else { // coll
        int u = max(U[row][col], U[n_row][n_col]);
        int d = min(D[row][col], D[n_row][n_col]);
        if (d - u - 1 >= h and !vis[n_row][n_col]) {
          q.push({n_row, n_col});
          vis[n_row][n_col] = true;
        }
      }
    }
  }
}

void run() {
  cin >> n >> m >> w >> h;
  swap(n, m);
  cin >> col_1 >> row_1 >> col_2 >> row_2;
  col_1++, col_2++, row_1++, row_2++;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      cin >> g[i][j];
      if (g[i][j] == '*') {
        f_row = i;
        f_col = j;
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    L[i][0] = 0;
    R[i][m + 1] = m + 1;
  }
  for (int j = 1; j <= m; j++) {
    U[0][j] = 0;
    D[n + 1][j] = n + 1;
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (g[i][j] == 'X') {
        U[i][j] = i;
        L[i][j] = j;
        continue;
      }
      U[i][j] = U[i - 1][j];
      L[i][j] = L[i][j - 1];
    }
  }
  for (int i = n; i >= 1; i--) {
    for (int j = m; j >= 1; j--) {
      if (g[i][j] == 'X') {
        D[i][j] = i;
        R[i][j] = j;
        continue;
      }
      D[i][j] = D[i + 1][j];
      R[i][j] = R[i][j + 1];
    }
  }
  bfs();
  cout << (vis[f_row][f_col] ? "YES" : "NO") << '\n';
}

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(nullptr);
  int t = 1;
  while (t--) {
    run();
  }
}
#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...