제출 #1342904

#제출 시각아이디문제언어결과실행 시간메모리
1342904AzeTurk810Toy (CEOI24_toy)C++20
100 / 100
135 ms40228 KiB
/*
Telebe of Adicto && Mamedov yani AzeTurk810
I see humans but no humanity
*/
#include <algorithm>
#include <cassert>
#include <iostream>
#include <queue>

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using ll = long long;
using namespace std;

#define ln '\n'
#define INFi 1e9
#define INFll 1e18

#ifdef ONPC
#include <algo.hpp>
#else
#define dbg(...)
#define dbg_out(...)
#endif

constexpr int N = 1000 + 505;

struct point {
    int x, y;
};

int H, W, K, L;
char g[N][N];
bool used[N][N];
int U[N][N], D[N][N], Le[N][N], Ri[N][N];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

inline void systemd() {
}

inline void build() {
    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            if (g[i][j] != 'X') {
                U[i][j] = U[i - 1][j] + 1;
                Le[i][j] = Le[i][j - 1] + 1;
            }
        }
    }
    for (int i = H; i >= 1; i--) {
        for (int j = W; j >= 1; j--) {
            if (g[i][j] != 'X') {
                D[i][j] = D[i + 1][j] + 1;
                Ri[i][j] = Ri[i][j + 1] + 1;
            }
        }
    }
}

bool can_exist(int r, int c) {
    if (r < 1 || r > H || c < 1 || c > W || g[r][c] == 'X')
        return false;
    if (Le[r][c] + Ri[r][c] - 1 < K) /// Horizontal
        return false;
    if (U[r][c] + D[r][c] - 1 < L) /// vertical
        return false;
    return true;
}

char solve() {
    if (!(cin >> W >> H >> K >> L)) {
        return 1;
    }

    int xh, yh, xv, yv;
    cin >> xh >> yh >> xv >> yv;
    point start = {yh + 1, xv + 1};
    point target;

    systemd();
    for (size_t i = 1; i <= H; i++) {
        for (size_t j = 1; j <= W; j++) {
            cin >> g[i][j];
            if (g[i][j] == '*') {
                target = {(int) i, (int) j};
            }
        }
    }

    build();

    { /// bfs
        queue<point> q;
        if (can_exist(start.x, start.y)) {
            used[start.x][start.y] = true;
            q.push(start);
        }


        while (!q.empty()) {
            point v = q.front();
            q.pop();

            if (v.x == target.x && v.y == target.y) {
                cout << "YES" << endl;
                return 0;
            }

            for (int i = 0; i < 4; i++) {
                int nr = v.x + dx[i];
                int nc = v.y + dy[i];

                if (can_exist(nr, nc)) {
                    bool can = false;
                    if (v.x == nr) { 
                        int wwww = min(U[v.x][v.y], U[nr][nc]) + min(D[v.x][v.y], D[nr][nc]) - 1;
                        if (wwww >= L)
                            can = true;
                    } else {
                        int wwww = min(Le[v.x][v.y], Le[nr][nc]) + min(Ri[v.x][v.y], Ri[nr][nc]) - 1;
                        if (wwww >= K)
                            can = true;
                    }

                    if (can && !used[nr][nc]) {
                        used[nr][nc] = true;
                        q.push({nr, nc});
                    }
                }
            }
        }
    }

    cout << "NO\n";
    return 0;
}

// Attack on titan<3

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    int t = 1e9;
    // cin >> t;
    for (int cases = 0; cases < t; cases++) {
        if (solve())
            break;
#ifdef ONPC
        cerr << "__________\n";
#endif
    }
}
// Just Imaginary
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⠀⠀⠀⢀⣴⣾⠀⠀⠀⡀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣦⣾⣿⣿⣿⣿⣿⡆⠁⠀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠀⡠⠂⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠠⠔⠚⣿⣿⣿⣿⣿⣦⡄⠀⠁⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⠠⠐⢂⠉⡀⣀⣤⣄⢻⣿⣿⡟⢈⡹⣿⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⡀⠄⠂⠈⠀⣶⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣷⡀⠀⡀⠐⠂⠐⢄
⠀⠀⠀⠀⠀⠀⠀⣿⣿⠟⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣀⣾⣷⠯⠀⠤⠤⠄⠈
⠀⠀⠀⠀⠀⠀⣼⣿⡟⠀⠀⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣰⣿⠋⠀⠀⢠⣾⣿⣿⣿⣿⣿⣭⠟⢻⣿⣿⣿⣿⡿⠁⠀⠀⠀⠀
⠀⠀⠀⣀⣶⡟⠁⠀⢾⣶⣿⠟⠉⠈⢻⣿⣿⣿⣦⣜⠀⠛⠛⠿⠁⠀⠀⠀⠀⠀
⠚⠻⠿⠿⡿⠁⠀⢠⣿⣿⠁⠀⣠⠖⠋⠉⠻⣿⣿⣿⣶⡀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣰⣿⡿⠃⠠⠊⠁⠀⠀⠀⠀⠈⢿⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⣴⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⣠⣾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⢀⣴⠾⠟⠛⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
*/
#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...