Submission #1342760

#TimeUsernameProblemLanguageResultExecution timeMemory
1342760valerianToy (CEOI24_toy)C++20
0 / 100
4 ms3996 KiB
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define endl '\n'
#define Valerian void
#define Valerian_or_Habil ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

using namespace std;

int pref[1505][1505];
int dist[1505][1505];
char grid[1505][1505];

Valerian solve() {
    int W, H, K, L;
    if (!(cin >> W >> H >> K >> L)) return;

    int xh, yh, xv, yv;
    cin >> xh >> yh >> xv >> yv;

    int tr = -1, tc = -1;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> grid[i][j];
            pref[i + 1][j + 1] = pref[i][j + 1] + pref[i + 1][j] - pref[i][j] + (grid[i][j] == 'X');
            dist[i][j] = -1;
            if (grid[i][j] == '*') {
                tr = i; tc = j;
            }
        }
    }

    int sr = yh, sc = xv;
    queue<pair<int, int>> q;
    q.push({sr, sc});
    dist[sr][sc] = 0;

    int dr[] = {0, 0, 1, -1};
    int dc[] = {1, -1, 0, 0};

    while (!q.empty()) {
        pair<int, int> curr = q.front();
        int r = curr.first;
        int c = curr.second;
        q.pop();

        if (r == tr && c == tc) {
            cout << "YES" << endl;
            return;
        }

        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];

            if (nr >= 0 && nr < H && nc >= 0 && nc < W && dist[nr][nc] == -1) {
                bool hor = false;
                int c_min = max(0, nc - K + 1);
                int c_max = min(W - K, nc);
                for (int j = c_min; j <= c_max; j++) {
                    int r1 = nr, c1 = j, r2 = nr, c2 = j + K - 1;
                    int cnt = pref[r2 + 1][c2 + 1] - pref[r1][c2 + 1] - pref[r2 + 1][c1] + pref[r1][c1];
                    if (cnt == 0) {
                        hor = true;
                        break;
                    }
                }

                if (!hor) continue;

                bool ver = false;
                int r_min = max(0, nr - L + 1);
                int r_max = min(H - L, nr);
                for (int j = r_min; j <= r_max; j++) {
                    int r1 = j, c1 = nc, r2 = j + L - 1, c2 = nc;
                    int cnt = pref[r2 + 1][c2 + 1] - pref[r1][c2 + 1] - pref[r2 + 1][c1] + pref[r1][c1];
                    if (cnt == 0) {
                        ver = true;
                        break;
                    }
                }

                if (ver) {
                    dist[nr][nc] = 0;
                    q.push({nr, nc});
                }
            }
        }
    }

    cout << "NO" << endl;
}

int main() {
    Valerian_or_Habil;
    solve();
    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...