#include <bits/stdc++.h>
#define int long long
using namespace std;
void dfs(int v, vector<vector<int>> &g, vector<bool> &uu) {
if (uu[v]) return;
uu[v] = 1;
for (int u : g[v]) dfs(u, g, uu);
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int w, h, k, l;
cin >> w >> h >> k >> l;
int xh, yh, xv, yv;
cin >> xh >> yh >> xv >> yv;
vector<string> a(h + 2);
for (int j = 0; j < w + 2; j++) {
a[0] += 'X';
a[h + 1] += 'X';
}
for (int i = 1; i <= h; i++) {
string t;
cin >> t;
a[i] = 'X' + t + 'X';
}
w += 2, h += 2;
int sx = xv + 1, sy = yh + 1;
int ex, ey;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (a[i][j] == '*') {
ex = j, ey = i;
}
}
}
vector<vector<int>> Bl(h, vector<int>(w)), Br(h, vector<int>(w)), Bu(h, vector<int>(w)),
Bd(h, vector<int>(w));
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
for (int x = j; x >= 0; x--) {
if (a[i][x] == 'X') {
Bl[i][j] = x;
break;
}
}
for (int x = j; x < w; x++) {
if (a[i][x] == 'X') {
Br[i][j] = x;
break;
}
}
for (int y = i; y >= 0; y--) {
if (a[y][j] == 'X') {
Bu[i][j] = y;
break;
}
}
for (int y = i; y < h; y++) {
if (a[y][j] == 'X') {
Bd[i][j] = y;
break;
}
}
}
}
vector<vector<int>> g(w * h); // y * w + x
for (int y = 0; y < h; y++) {
for (int x = 0; x < w - 1; x++) {
if (a[y][x] != 'X' && a[y][x + 1] != 'X') {
int U = max(Bu[y][x], Bu[y][x + 1]);
int D = min(Bd[y][x], Bd[y][x + 1]);
if (D - U - 1 >= l) {
g[y * w + x].push_back(y * w + (x + 1));
g[y * w + (x + 1)].push_back(y * w + x);
}
}
}
}
for (int y = 0; y < h - 1; y++) {
for (int x = 0; x < w; x++) {
if (a[y][x] != 'X' && a[y + 1][x] != 'X') {
int L = max(Bl[y][x], Bl[y + 1][x]);
int R = min(Br[y][x], Br[y + 1][x]);
if (R - L - 1 >= k) {
g[y * w + x].push_back((y + 1) * w + x);
g[(y + 1) * w + x].push_back(y * w + x);
}
}
}
}
vector<bool> uu(w * h);
dfs(sy * w + sx, g, uu);
cout << (uu[ey * w + ex] ? "YES\n" : "NO\n");
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |