Submission #1345738

#TimeUsernameProblemLanguageResultExecution timeMemory
1345738cpismayilmmdv985Toy (CEOI24_toy)C++20
0 / 100
10 ms18816 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;
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);
}

inline bool isfree(const int &x, const int &y) {
   return x >= 1 && y >= 1 && x <= H && y <= W && grid[x][y] != 'X';
}

void dfs(const int &xh, const int &yh, const int &xv, const int &yv, const int &x, const int &y) {
   vis[x][y] = true;
   if (x == targetX && y == targetY) {
      cout << "YES";
      exit(0);
   }
   for (int d = 0; d < 4; d++) {
      int tox = x + DX[d], toy = y + DY[d];
      if (!isfree(tox, toy))  continue;
      if (vis[tox][toy])   continue;
      if (DX[d] == 1) {
         // down -> horizontal line slid down 
         if (isValid(0, xh + 1, yh))   dfs(xh + 1, yh, xv, yv, tox, toy);
         else {
            for (int i = 1; i <= K; i++) {
               if (!isValid(0, xh, yh + i))  break;
               if (isValid(0, xh + 1, yh + i))  dfs(xh + 1, yh + i, xv, yv, tox, toy);
            }
            for (int i = 1; i <= K; i++) {
               if (!isValid(0, xh, yh - i))  break;
               if (isValid(0, xh + 1, yh - i))  dfs(xh + 1, yh - i, xv, yv, tox, toy);
            }
         }
      } else if (DX[d] == -1) {
         // up -> horizontal line slid up
         if (isValid(0, xh - 1, yh))   dfs(xh - 1, yh, xv, yv, tox, toy);
         else {
            for (int i = 1; i <= K; i++) {
               if (!isValid(0, xh, yh + i))  break;
               if (isValid(0, xh - 1, yh + i))  dfs(xh - 1, yh + i, xv, yv, tox, toy);
            }
            for (int i = 1; i <= K; i++) {
               if (!isValid(0, xh, yh - i))  break;
               if (isValid(0, xh - 1, yh - i))  dfs(xh - 1, yh - i, xv, yv, tox, toy);
            }
         }
      } else if (DY[d] == 1) {
         // right -> vertical line slid right
         if (isValid(1, xv, yv + 1))   dfs(xh, yh, xv, yv + 1, tox, toy);
         else {
            for (int i = 1; i <= L; i++) {
               if (!isValid(1, xv + i, yv))  break;
               if (isValid(1, xv + i, yv + 1))  dfs(xh, yh, xv + i, yv + 1, tox, toy);
            }
            for (int i = 1; i <= L; i++) {
               if (!isValid(1, xv - i, yv))  break;
               if (isValid(1, xv - i, yv + 1))  dfs(xh, yh, xv - i, yv + 1, tox, toy);
            }
         }
      } else {
         // left -> vertical line slid left
         if (isValid(1, xv, yv - 1))   dfs(xh, yh, xv, yv - 1, tox, toy);
         else {
            for (int i = 1; i <= L; i++) {
               if (!isValid(1, xv + i, yv))  break;
               if (isValid(1, xv + i, yv - 1))  dfs(xh, yh, xv + i, yv - 1, tox, toy);
            }
            for (int i = 1; i <= L; i++) {
               if (!isValid(1, xv - i, yv))  break;
               if (isValid(1, xv - i, yv - 1))  dfs(xh, yh, xv - i, yv - 1, tox, toy);
            }
         }
      }
   }
}

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');
      }
   array<int, 2> inter = inter_point(XH, YH, XV, YV);
   dfs(XH, YH, XV, YV, inter[0], inter[1]);
   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...