QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#640773#9164. ToyCrafticat#0 3ms5548kbC++142.1kb2024-10-14 15:56:102024-10-14 15:56:11

Judging History

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

  • [2024-10-14 15:56:11]
  • 评测
  • 测评结果:0
  • 用时:3ms
  • 内存:5548kb
  • [2024-10-14 15:56:10]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
template<typename T>
using V = vector<T>;

int w, h, k, l;
V<V<V<V<bool>>>> vis;
V<V<bool>> grid;
int dx[] = {0,1,-1,0};
int dy[] = {1,0,0,-1};
int visA = 0;

bool outOfB(int x, int y) {
    if (x >= w || y >= h || x < 0 || y < 0) return true;
    return false;
}

bool validPosition(int x, int y, int x2, int y2) {
    for (int i = x; i < x + k; ++i) {
        if (outOfB(i,y)) return false;
        if (!grid[i][y]) return false;
    }
    for (int i = y2; i < y2 + l; ++i) {
        if (outOfB(x2,i)) return false;
        if (!grid[x2][i]) return false;
    }
    return true;
}

void bfs(int x, int y, int x2 ,int y2) {
    if (!validPosition(x, y, x2, y2)) return;
    if (vis[x][y][x2][y2]) return;
    vis[x][y][x2][y2] = true;
    visA++;

    for (int i = 0; i < 4; ++i) {
        bfs(x + dx[i], y + dy[i], x2,y2);
    }
    for (int i = 0; i < 4; ++i) {
        bfs(x, y, x2 + dx[i],y2 + dy[i]);
    }
}

int main() {
    cin >> w >> h >> k >> l;

    int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
    int targetX, targetY;

    vis.resize(w, V<V<V<bool>>>(h,V<V<bool>>(w, V<bool>(h))));
    grid.resize(w, V<bool>(h));

    for (int i = 0; i < h; ++i) {
        string str; cin >> str;
        for (int j = 0; j < w; ++j) {
            grid[j][i] = str[j] != 'X';
            if (str[j] == '*') {
                targetX = j;
                targetY = i;
            }
        }
    }

    for (int i = targetX - k + 1; i <= targetX; ++i) {
        for (int j = i; j < i + k; ++j) {
            for (int m = targetY - l + 1; m <= targetY; ++m) {
                bfs(i, targetY, j, m);
            }
        }
    }

    for (int i = targetY - l + 1; i <= targetY; ++i) {
        for (int j = i; j < i + l; ++j) {
            for (int m = targetX - k + 1; m <= targetX; ++m) {
                bfs(m,j,targetX,i );
            }
        }
    }

    if (visA == 1) {
        cout << "NO";
        return 0;
    }
    cout << (vis[x1][y1][x2][y2] ? "YES" : "NO");

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 14
Accepted
time: 3ms
memory: 5548kb

input:

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

output:

YES

result:

ok answer is YES

Test #2:

score: 0
Time Limit Exceeded

input:

50 50 22 14
26 34 36 33
..................................................
..................................................
..................................................
..................................................
..................................................
........................

output:


result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Time Limit Exceeded

Test #89:

score: 0
Time Limit Exceeded

input:

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

output:


result:


Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%