제출 #1345414

#제출 시각아이디문제언어결과실행 시간메모리
1345414cpismayilmmdv985Toy (CEOI24_toy)C++20
35 / 100
505 ms513252 KiB
#ifdef LOCAL
#include ".debug.hpp"
#else
#define debug(...) 42
#endif
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;

const int MXN = 5000;
const int DX[] = {1, -1, 0, 0}, DY[] = {0, 0, 1, -1};
int W, H, K, L, pref[MXN][MXN], targetX = 0, targetY = 0, cell[MXN][MXN];
char grid[MXN][MXN];
bool vis[MXN][MXN], used[MXN][MXN];

inline int cnt(const int &x1, const int &y1, const int &x2, const int &y2) {
   return pref[x2][y2] - pref[x2][y1 - 1] - pref[x1 - 1][y2] + pref[x1 - 1][y1 - 1];
}

array<int, 2> inter_point(const int &xh, const int &yh, const int &xv, const int &yv) {
   int xh1 = xh, yh1 = yh + K - 1, xv1 = xv + L - 1, yv1 = yv;
   if (yh <= yv && yv <= yh1 && xv <= xh && xh <= xv1) 
      return {xh, yv};
   return {-1, -1};  
}

bool isValid(const int &type, const int &x, const int &y) {
   if (x < 1 || y < 1 || x > H || y > W)  return false;
   int x1, y1;
   if (!type)  // horizontal line check
      x1 = x, y1 = y + K - 1;
   else        // vertical line check
      x1 = x + L - 1, y1 = y;
   if (x1 < 1 || y1 < 1 || x1 > H || y1 > W) return false;
   return !cnt(x, y, x1, y1);
}

void dfs(const int &xh, const int &yh, const int &xv, const int &yv) {
   used[cell[xh][yh]][cell[xv][yv]] = true;
   array<int, 2> inter = inter_point(xh, yh, xv, yv);
   vis[inter[0]][inter[1]] = true;
   if (inter[0] == targetX && inter[1] == targetY) {
      cout << "YES\n";
      exit(0);
   }
   for (int d = 0; d < 4; d++) {
      int txh = xh + DX[d], tyh = yh + DY[d];
      if (isValid(0, txh, tyh) && inter_point(txh, tyh, xv, yv)[0] != -1 && 
            !used[cell[txh][tyh]][cell[xv][yv]])
         dfs(txh, tyh, xv, yv);
   }
   for (int d = 0; d < 4; d++) {
      int txv = xv + DX[d], tyv = yv + DY[d];
      if (isValid(1, txv, tyv) && inter_point(xh, yh, txv, tyv)[0] != -1 && 
            !used[cell[xh][yh]][cell[txv][tyv]])
         dfs(xh, yh, txv, tyv);
   }
}

signed main() {
#ifndef VOID
   cin.tie(nullptr)->sync_with_stdio(false);
#endif

   int XH, YH, XV, YV;
   cin >> W >> H >> K >> L >> XH >> YH >> XV >> YV, XH++, YH++, XV++, YV++;
   swap(XH, YH), swap(XV, YV);
   for (int i = 1; i <= H; i++)
      for (int j = 1; j <= W; j++) {
         cin >> grid[i][j];
         if (!targetX && grid[i][j] == '*')  targetX = i;
         if (!targetY && grid[i][j] == '*')  targetY = j;
      }
   int id = 0;
   for (int i = 1; i <= H; i++)
      for (int j = 1; j <= W; j++) {
         pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + (grid[i][j] == 'X');
         cell[i][j] = id++;
      }
   dfs(XH, YH, XV, YV);
   cout << "NO\n";

   return 0;
}
#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...