QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#640773 | #9164. Toy | Crafticat# | 0 | 3ms | 5548kb | C++14 | 2.1kb | 2024-10-14 15:56:10 | 2024-10-14 15:56:11 |
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%