제출 #1343605

#제출 시각아이디문제언어결과실행 시간메모리
1343605JohanToy (CEOI24_toy)C++20
0 / 100
1 ms580 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e3 + 5;
const int MOD = 1e9 + 7;
char a[N][N];
int pr1[N][N], pr2[N][N];
int n, m, k, l, end1, end2;
vector < int > dx{1, -1, 0, 0};
vector < int > dy{0, 0, -1, 1};
map < array < int , 4 > , bool > vis;
bool can_go1(int x1, int y1, int k){
  if(x1 <= 0 || x1 > n || y1 <= 0 || y1 > m)
    return false;
  if(a[x1][y1] == 'X')
    return false;
  int x2 = x1, y2 = y1 + k - 1;
  if(y2 > m)return false;
  if(pr1[x2][y2] - pr1[x1][y1 - 1] > 0)return false;
  return (vis.count({x1, y1, x2, y2}) == 0);
}
bool can_go2(int x1, int y1, int k){
  if(x1 <= 0 || x1 > n || y1 <= 0 || y1 > m)
    return false;
  if(a[x1][y1] == 'X')
    return false;
  int x2 = x1 + k - 1, y2 = y1;
  if(x2 > n)return false;
  if(pr2[x2][y2] - pr2[x1 - 1][y1] > 0)return false;
  return (vis.count({x1, y1, x2, y2}) == 0);
}
array < int , 2 > next1(int x, int y, int sz){
  return {x, y + sz - 1};
}
array < int , 2 > next2(int x, int y, int sz){
  return {x + sz - 1, y};
}
bool bfs1(int x, int y, int sz){
  vis.clear();
  queue < array < int , 2 > > q;
  auto [nxt_x, nxt_y] = next1(x, y, sz);
  q.push({x, y});
  vis[{x, y, nxt_x, nxt_y}] = true;
  while(q.size() > 0){
    auto [cur_x, cur_y] = q.front();
    q.pop();
    for(int d = 0; d < 4; d++){
      int fx = cur_x + dx[d];
      int fy = cur_y + dy[d];
      if(can_go1(fx, fy, sz) == true){
        q.push({fx, fy});
        auto [nxt_x, nxt_y] = next1(fx, fy, sz);
        vis[{fx, fy, nxt_x, nxt_y}] = true;
      }
    }
  }
  for(auto [xy, is] : vis){
    auto [x1, y1, x2, y2] = xy;
    if(!is)continue;
    if(x1 == end1 && y1 <= end2 && end2 <= y2)
      return true;
  }
  return false;
}
bool bfs2(int x, int y, int sz){
  vis.clear();
  queue < array < int , 2 > > q;
  auto [nxt_x, nxt_y] = next2(x, y, sz);
  q.push({x, y});
  vis[{x, y, nxt_x, nxt_y}] = true;
  while(q.size() > 0){
    auto [cur_x, cur_y] = q.front();
    q.pop();
    for(int d = 0; d < 4; d++){
      int fx = cur_x + dx[d];
      int fy = cur_y + dy[d];
      if(can_go2(fx, fy, sz) == true){
        q.push({fx, fy});
        auto [nxt_x, nxt_y] = next2(fx, fy, sz);
        vis[{fx, fy, nxt_x, nxt_y}] = true;
      }
    }
  }
  for(auto [xy, is] : vis){
    auto [x1, y1, x2, y2] = xy;
    if(!is)continue;
    // cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << "\n";
    if(y1 == end2 && x1 <= end1 && end1 <= x2)
      return true;
  }
  return false;
}
signed main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m >> k >> l;
  int x1, y1, x2, y2;
  cin >> x1 >> y1 >> x2 >> y2;
  swap(n, m);
  x1++, y1++, x2++, y2++;
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
      cin >> a[i][j];
      pr1[i][j] = pr1[i][j - 1] + (int)(a[i][j] == 'X');
      pr2[i][j] = pr2[i - 1][j] + (int)(a[i][j] == 'X');
      if(a[i][j] == '*'){
        end1 = i, end2 = j;
      }
    }
  }
  if(bfs1(x1, y1, k) && bfs2(x2, y2, l)){
    cout << "YES\n";
  }
  else {
    cout << "NO\n";
  }
}
#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...