제출 #1364894

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

const int MAXN = 1510;

int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};

int marc[MAXN][MAXN], cnt[MAXN][MAXN];

int pre_row[MAXN][MAXN], pre_col[MAXN][MAXN];

int nxt_row[MAXN][MAXN], nxt_col[MAXN][MAXN];

char m[MAXN][MAXN];

int w, h, k, l;

bool check(int x, int y){
  return 0 <= x && x < h && 0 <= y && y < w;
}

bool can_reach(int x, int y, int nx, int ny){

  if(m[x][y] == 'X' || m[nx][ny] == 'X') return false;

  bool ans = true;

  // k eh o tamanho horizontal
  // l eh o tamanho vertical

  int cur_window = 0;

  if(nx == x){
    cur_window = nxt_row[x][y] - pre_row[x][y] + 1;
  } else cur_window = nxt_col[x][y] - pre_col[x][y] + 1;

  if(nx == x){
    ans &= (cur_window >= k);
  } else ans &+ (cur_window >= l);

  // agora checo o outro metal

  int lx = 0, rx = 0;

  if(nx == x){
    // entao agora eh vertical
    lx = max(pre_col[x][y], pre_col[nx][ny]);
    rx = min(nxt_col[x][y], nxt_col[nx][ny]);

  } else{

    lx = max(pre_row[x][y], pre_row[nx][ny]);
    rx = min(nxt_row[x][y], nxt_row[nx][ny]);

  }

  cur_window = rx - lx + 1;

  if(nx == x){
    ans &= (cur_window >= l);
  } else ans &= (cur_window >= k);

  // if(ans) cout << x << " " << y << " -> " << nx << " " << ny << endl;
  return ans;

}

void dfs(int x, int y){

  marc[x][y] = 1;

  for(int k=0; k<4; k++){

    int nx = x + dx[k], ny = y + dy[k];

    if(!check(nx, ny) || marc[nx][ny]) continue;
    if(!can_reach(x, y, nx, ny)) continue;

    dfs(nx, ny);

  }

}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> w >> h >> k >> l;

  int xh, yh; cin >> xh >> yh;

  int xv, yv; cin >> xv >> yv;

  for(int j=yh; j<(yh + k); j++) cnt[xh][j] ++;

  for(int i=xv; i<(xv + l); i++) cnt[i][yv] ++;

  int x_s = 0, y_s = 0;

  int x_t = 0, y_t = 0;

  for(int i=0; i<h; i++){
    for(int j=0; j<w; j++){

      cin >> m[i][j];

      if(m[i][j] == '*'){
        x_t = i;
        y_t = j;
      }

      if(cnt[i][j] > 1){
        x_s = i;
        y_s = j;
      }

    }
  }

  for(int i=0; i<h; i++){
    for(int j=0; j<w; j++){

      if(m[i][j] == 'X'){

        pre_row[i][j] = i + 1;
        pre_col[i][j] = j + 1;

      } else{

        pre_row[i][j] = (i > 0 ? pre_row[i - 1][j] : 0);
        pre_col[i][j] = (j > 0 ? pre_col[i][j - 1] : 0);

      }

    }
  }

  for(int i=(h - 1); i>=0; i--){
    for(int j=(w - 1); j>=0; j--){

      if(m[i][j] == 'X'){

        nxt_row[i][j] = i - 1;
        nxt_col[i][j] = j - 1;

      } else{

        nxt_row[i][j] = (i < h - 1 ? nxt_row[i + 1][j] : h - 1);
        nxt_col[i][j] = (j < w - 1 ? nxt_col[i][j + 1] : w - 1);

      }

    }
  }

  dfs(x_s, y_s);

  cout << (marc[x_t][y_t] ? "YES" : "NO") << "\n";

  return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…