QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #532848 | #9164. Toy | Dimash# | 0 | 7ms | 19168kb | C++23 | 3.0kb | 2024-08-25 13:17:23 | 2024-08-25 13:17:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e3 + 12, MOD = (int)1e9 + 7;
const int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
int n, m, k, l, x, y;
int a[N][N],ph[N][N],nh[N][N],pv[N][N],nv[N][N];
bool vis[N][N];
bool ok(int X,int Y) {
return (min(X,Y) >= 1 && X <= n && Y <= m && !a[X][Y]);
}
int inter(int l,int r,int l1,int r1) {
// cout << l << ' ' << r << ' ' << l1 << ' ' << r1 << '\n';
return max(0,min(r,r1) - max(l,l1) + 1);
}
void test(){
cin >> n >> m >> l >> k;
swap(n,m);
int x1, y1;
cin >> y >> x >> y1 >> x1;
y = y1;
x++;
y++;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
char t;
cin >> t;
if(t == 'X') {
a[i][j] = 1;
}
if(t == '*') {
x1 = i;
y1 = j;
}
if(a[i][j]) {
ph[i][j] = j;
} else {
ph[i][j] = ph[i][j - 1];
}
}
nh[i][m + 1] = m + 1;
for(int j = m;j >= 1;j--) {
if(a[i][j]) {
nh[i][j] = j;
} else {
nh[i][j] = nh[i][j + 1];
}
}
}
for(int i = 1;i <= m;i++) {
for(int j = 1; j <= n; j++) {
if(a[j][i]) {
pv[j][i] = j;
} else {
pv[j][i] = pv[j - 1][i];
}
// cout << j << ' ' << i << ' ' << pv[j][i] << '\n';
}
nv[n + 1][i] = n + 1;
for(int j = n; j >= 1; j--) {
if(a[j][i]) {
nv[j][i] = j;
} else {
nv[j][i] = nv[j + 1][i];
}
}
}
queue<pair<int,int>> q;
q.push({x,y});
vis[x][y] = 1;
while(!q.empty()) {
auto [x_,y_] = q.front();
// cout << x_ << ' ' << y_ << '\n';
if(x_ == x1 && y_ == y1) {
cout << "Yes\n";
return;
}
q.pop();
for(int i = 0; i < 4; i++) {
int _x = x_ + dx[i],_y = y_ + dy[i];
if(!ok(_x,_y) || vis[_x][_y]) continue;
// cout << _x << ' ' << _y << '\n';
if(x != _x) {
if(inter(ph[x_][y_] + 1,nh[x_][y_] - 1,ph[_x][_y] + 1,nh[_x][_y] - 1) >= k) {
vis[_x][_y] = 1;
q.push({_x,_y});
}
} else {
// cout << inter(pv[x_][y_] + 1,nv[x_][y_] - 1,pv[_x][_y] + 1,nv[_x][_y] - 1) << ' ' << "x\n";
if(inter(pv[x_][y_] + 1,nv[x_][y_] - 1,pv[_x][_y] + 1,nv[_x][_y] - 1) >= l) {
vis[_x][_y] = 1;
q.push({_x,_y});
}
}
}
}
cout << "No\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t = 1;
// cin >> t;
while(t--) {
test();
}
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 14
Accepted
time: 1ms
memory: 8048kb
input:
32 16 23 15 3 8 4 1 ................................ ................................ ................................ ................................ ................................ *............................... ................................ ................................ ...................
output:
Yes
result:
ok answer is YES
Test #2:
score: 14
Accepted
time: 1ms
memory: 8120kb
input:
50 50 22 14 26 34 36 33 .................................................. .................................................. .................................................. .................................................. .................................................. ........................
output:
Yes
result:
ok answer is YES
Test #3:
score: 14
Accepted
time: 0ms
memory: 8448kb
input:
50 50 50 50 0 18 2 0 .................................................. ...............................................X.. .................................................. .................................................. .................................................. ...........................
output:
No
result:
ok answer is NO
Test #4:
score: 0
Wrong Answer
time: 2ms
memory: 10160kb
input:
5 47 4 47 1 25 3 0 .X... ..... ..... .X... ..... ..... ..... ..... ..... ..... ..... ..... ..*.. ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... X.... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... .....
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: 9
Accepted
time: 1ms
memory: 8052kb
input:
105 31 8 4 70 27 75 26 ......................................................................................................... ......................................................................................................... ....................................................................
output:
Yes
result:
ok answer is YES
Test #90:
score: 9
Accepted
time: 0ms
memory: 17196kb
input:
300 300 4 8 231 246 234 240 ...................................................................................................................................................................................................................................................................................
output:
Yes
result:
ok answer is YES
Test #91:
score: 9
Accepted
time: 5ms
memory: 19168kb
input:
300 300 10 10 151 143 155 137 .................................................................................................................................................................................................................................................................................
output:
Yes
result:
ok answer is YES
Test #92:
score: 9
Accepted
time: 0ms
memory: 10780kb
input:
159 68 6 2 95 54 98 54 .........................................................................X..................................................................................... ..........................X..................................................X..........................................
output:
Yes
result:
ok answer is YES
Test #93:
score: 9
Accepted
time: 7ms
memory: 18440kb
input:
300 300 10 10 11 147 12 143 .....................................................................X.................X.......................................*X..............................................X...................................................................................................
output:
Yes
result:
ok answer is YES
Test #94:
score: 9
Accepted
time: 6ms
memory: 18316kb
input:
300 300 10 10 289 237 298 236 .........................................................................................X.......................................................................................................................................................................................
output:
Yes
result:
ok answer is YES
Test #95:
score: 9
Accepted
time: 3ms
memory: 11412kb
input:
277 111 6 9 109 9 112 5 ...................X..XX...........X.......X..................X...X.......X........X......X...........X....................X.......................X..X..X.........XX...................X..............X..........X..................X................X...................X............
output:
No
result:
ok answer is NO
Test #96:
score: 0
Wrong Answer
time: 3ms
memory: 17696kb
input:
300 300 6 6 126 5 131 1 .......X............XX..............X...X....XX..........X..X........X.X...X...........X.................X...............X..............X.....XX.............X....................................XX....X................X........X...................X.....X..........................
output:
Yes
result:
wrong answer expected NO, found YES
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%