Submission #1342787

#TimeUsernameProblemLanguageResultExecution timeMemory
1342787po_rag526Toy (CEOI24_toy)C++20
100 / 100
192 ms141808 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
#define len(x) (ll)x.size()
const ll inf = 1e9, infl = 1e18;
const ll MOD = 1e9 + 7;
const ll maxn = 2e3 + 5;
ll n, m, k = 0;

array<ll, 2> s, u, l, e;
ll a[maxn][maxn], le[maxn][maxn], ri[maxn][maxn], up[maxn][maxn], dw[maxn][maxn], dp[maxn][maxn];
void _() {
  cin >> m >> n >> l[1] >> l[0];
  cin >> s[1] >> s[0] >> u[1] >> u[0];

  s[0] ++, s[1] ++, u[0] ++, u[1] ++;
  for(ll i = 1; i <= n; i ++){
    char ch;
    for(ll j = 1; j <= m; j ++){
      cin >> ch;
      a[i][j] = ch == 'X';
      if(ch == '*') e = {i, j};
    }
  }
  
  for(ll i = 1; i <= n + 1; i ++) for(ll j = 1; j <= m + 1; j ++) up[i][j] = 0, le[i][j] = 0, ri[i][j] = m + 1, dw[i][j] = n + 1;

  for(ll i = 1; i <= n; i ++){
    for(ll j = 1; j <= m; j ++){
      if(a[i][j]){
        le[i][j] = j;
        up[i][j] = i;
      } else {
        le[i][j] = le[i][j - 1];
        up[i][j] = up[i - 1][j];
      }
    }
  }
  
  for(ll i = n; i >= 1; i --){
    for(ll j = m; j >= 1; j --){
      if(a[i][j]){
        ri[i][j] = j;
        dw[i][j] = i;
      } else{
        ri[i][j] = ri[i][j + 1];
        dw[i][j] = dw[i + 1][j];
      }
    }
  }

  // for(ll i = 1; i <= n; i ++, cout << '\n') for(ll j = 1; j <= m; j ++) cout << up[i][j] << ' '; cout << '\n';
  // for(ll i = 1; i <= n; i ++, cout << '\n') for(ll j = 1; j <= m; j ++) cout << dw[i][j] << ' '; cout << '\n';
  // for(ll i = 1; i <= n; i ++, cout << '\n') for(ll j = 1; j <= m; j ++) cout << le[i][j] << ' '; cout << '\n';
  // for(ll i = 1; i <= n; i ++, cout << '\n') for(ll j = 1; j <= m; j ++) cout << ri[i][j] << ' ';

  queue<array<ll, 2>> q;
  q.push({s[0], u[1]});
  dp[s[0]][u[1]] = 1;
  while(!q.empty()){
    auto [x, y] = q.front(); q.pop();
    if(y + 1 <= m and min(dw[x][y], dw[x][y + 1]) - max(up[x][y], up[x][y + 1]) - 1 >= l[0]){
      if(!dp[x][y + 1]){
        dp[x][y + 1] = 1;
        q.push({x, y + 1});
      }
    }
    if(y - 1 >= 1 and min(dw[x][y], dw[x][y - 1]) - max(up[x][y], up[x][y - 1]) - 1 >= l[0]){
      if(!dp[x][y - 1]){
        dp[x][y - 1] = 1;
        q.push({x, y - 1});
      }
    }
    if(x + 1 <= n and min(ri[x][y], ri[x + 1][y]) - max(le[x][y], le[x + 1][y]) - 1 >= l[1]){
      if(!dp[x + 1][y]){
        dp[x + 1][y] = 1;
        q.push({x + 1, y});
      }
    }
    if(x - 1 >= 1 and min(ri[x][y], ri[x - 1][y]) - max(le[x][y], le[x - 1][y]) - 1 >= l[1]){
      if(!dp[x - 1][y]){
        dp[x - 1][y] = 1;
        q.push({x - 1, y});
      }
    }
  }
  if(dp[e[0]][e[1]]) cout << "YES\n";
  else cout << "NO\n";
}
signed main() {
  cin.tie(0)->sync_with_stdio(0);
  ll t = 1;
  // cin >> t;
  while(t --) _();
}
#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...