Submission #1346050

#TimeUsernameProblemLanguageResultExecution timeMemory
1346050cpismayilmmdv985Toy (CEOI24_toy)C++20
100 / 100
174 ms220844 KiB
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int W, H, K, L;
vector<vector<int>> obstacles_row, obstacles_col;
vector<vector<int>> visited;

pair<int, int> get_horizontal_range(int r, int c) {
    if (r < 0 || r >= H || c < 0 || c >= W) return {0, -1};
    auto it = upper_bound(obstacles_row[r].begin(), obstacles_row[r].end(), c);
    int right_wall = *it - 1;
    it--;
    int left_wall = *it + 1;
    return {left_wall, right_wall};
}

pair<int, int> get_vertical_range(int r, int c) {
    if (r < 0 || r >= H || c < 0 || c >= W) return {0, -1};
    auto it = upper_bound(obstacles_col[c].begin(), obstacles_col[c].end(), r);
    int bottom_wall = *it - 1;
    it--;
    int top_wall = *it + 1;
    return {top_wall, bottom_wall};
}

int calculate_overlap(pair<int, int> range1, pair<int, int> range2) {
    int start = max(range1.first, range2.first);
    int end = min(range1.second, range2.second);
    return max(0, end - start + 1);
}

void dfs(int r, int c) {
    if (visited[r][c]) return;
    visited[r][c] = 1;
    pair<int, int> cur_h_range = get_horizontal_range(r, c);
    pair<int, int> cur_v_range = get_vertical_range(r, c);
    pair<int, int> next_h_range = get_horizontal_range(r + 1, c);
    if (calculate_overlap(cur_h_range, next_h_range) >= K) {
        if (r + 1 <= cur_v_range.second) {
            dfs(r + 1, c);
        }
    }
    pair<int, int> prev_h_range = get_horizontal_range(r - 1, c);
    if (calculate_overlap(cur_h_range, prev_h_range) >= K) {
        if (r - 1 >= cur_v_range.first) {
            dfs(r - 1, c);
        }
    }
    pair<int, int> next_v_range = get_vertical_range(r, c + 1);
    if (calculate_overlap(cur_v_range, next_v_range) >= L) {
        if (c + 1 <= cur_h_range.second) { 
            dfs(r, c + 1);
        }
    }
    pair<int, int> prev_v_range = get_vertical_range(r, c - 1);
    if (calculate_overlap(cur_v_range, prev_v_range) >= L) {
        if (c - 1 >= cur_h_range.first) {
            dfs(r, c - 1);
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int startH_c, startH_r, startV_c, startV_r;
    cin >> W >> H >> K >> L;
    cin >> startH_c >> startH_r >> startV_c >> startV_r;
    obstacles_row.assign(H, vector<int>());
    obstacles_col.assign(W, vector<int>());
    for (int i = 0; i < W; i++) obstacles_col[i].push_back(-1);
    int target_r = -1, target_c = -1;
    for (int i = 0; i < H; i++) {
        obstacles_row[i].push_back(-1);
        string row_str; cin >> row_str;
        for (int j = 0; j < W; j++) {
            if (row_str[j] == 'X') {
                obstacles_row[i].push_back(j);
                obstacles_col[j].push_back(i);
            }
            if (row_str[j] == '*') { target_r = i; target_c = j; }
        }
        obstacles_row[i].push_back(W);
    }
    for (int i = 0; i < W; i++) obstacles_col[i].push_back(H);
    visited.assign(H, vector<int>(W, 0));
    dfs(startH_r, startV_c);
    if (visited[target_r][target_c]) cout << "YES" << endl;
    else cout << "NO" << endl;

    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...