QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#497858#9164. ToyQwerty1232#0 0ms3864kbC++232.9kb2024-07-29 19:35:402024-07-29 19:35:40

Judging History

你现在查看的是最新测评结果

  • [2024-07-29 19:35:40]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:3864kb
  • [2024-07-29 19:35:40]
  • 提交

answer

#include <bits/stdc++.h>

int32_t main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    std::cin >> n >> m;
    std::swap(n, m);
    int K, L;
    std::cin >> K >> L;
    std::vector<std::string> input(n);
    for (auto& s : input) {
        std::cin >> s;
    }
    std::pair<int, int> ph, pv;
    std::cin >> ph.first >> ph.second >> pv.first >> pv.second;
    std::swap(ph.first, ph.second);
    std::swap(pv.first, pv.second);

    std::pair<int, int> tg;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (input[i][j] == '*') {
                tg = {i, j};
            }
        }
    }
    std::vector<std::vector<int>> prf(n + 1, std::vector<int>(m + 1));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            prf[i + 1][j + 1] = input[i][j] + prf[i][j + 1] + prf[i + 1][j] - prf[i][j];
        }
    }

    auto get_sum = [&](char tp, std::pair<int, int> p) {
        std::pair<int, int> p2(p.first + (tp == 'h' ? 1 : K), p.second + (tp == 'h' ? L : 1));
        if (p.first < 0 || p.second < 0 || n < p2.first || m < p2.second) {
            return 1;
        }
        int res = prf[p2.first][p2.second] - prf[p.first][p2.second] - prf[p2.first][p.second] + prf[p.first][p.second];
        return res;
    };
    auto check_tg = [&](char tp, std::pair<int, int> p) {
        std::pair<int, int> p2(p.first + (tp == 'h' ? 1 : K), p.second + (tp == 'h' ? L : 1));
        if (p.first < 0 || p.second < 0 || n < p2.first || m < p2.second) {
            return false;
        }
        return p.first <= tg.first && tg.first < p2.first && p.second <= tg.second && tg.second < p2.second;
    };

    std::vector<int> rv(n * m), rh(n * m);
    for (char ch : std::string{"vh"}) {
        auto& vec = ch == 'h' ? rh : rv;
        std::vector<int> stack;
        stack.push_back((ch == 'h') ? ph.first * m + ph.second : pv.first * m + pv.second);
        while (stack.size()) {
            int v = stack.back();
            stack.pop_back();
            if (!vec[v]) {
                vec[v] = 1;
                auto [x, y] = div(v, m);
                for (auto [dx, dy] : std::array<std::pair<int, int>, 4>{{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}}) {
                    int x2 = x + dx, y2 = y + dy;
                    if (get_sum(ch, {x2, y2}) == 0) {
                        stack.push_back(x2 * m + y2);
                    }
                }
            }
        }
    }

    bool suc1 = false, suc2 = false;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            suc1 |= rv[i * m + j] && check_tg('v', {i, j});
            suc2 |= rh[i * m + j] && check_tg('h', {i, j});
        }
    }

    if (suc1 && suc2) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3464kb

input:

32 16 23 15
3 8 4 1
................................
................................
................................
................................
................................
*...............................
................................
................................
...................

output:

NO

result:

wrong answer expected YES, found NO

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #89:

score: 0
Wrong Answer
time: 0ms
memory: 3864kb

input:

105 31 8 4
70 27 75 26
.........................................................................................................
.........................................................................................................
....................................................................

output:

NO

result:

wrong answer expected YES, found NO

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%