QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#676985 | #7699. Pearls | new_game_plus_players# | AC ✓ | 708ms | 3888kb | C++14 | 2.5kb | 2024-10-26 08:12:24 | 2024-10-26 08:12:24 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 65;
const int dx[4] = {0, -1, 1, 0};
const int dy[4] = {1, 0, 0, -1};
const char ch[4] = {'E', 'N', 'S', 'W'};
int tot, n, m, sx, sy;
char s[MAXN], ret[MAXN];
int vis[MAXN][MAXN];
void work(int depth, int x, int y, int flg) { // flg: 0 -> no limit, 1 -> straight, 2 -> turn
int steps = tot + 1 - depth;
if (steps < abs(x - sx) + abs(y - sy)) return;
if (depth > tot) {
if (flg == 1 && ret[tot] != ret[1]) return;
if (flg == 2 && ret[tot] == ret[1]) return;
if (s[1] == 'B' && ret[tot] == ret[1]) return;
if (s[1] == 'W' && ret[tot] != ret[1]) return;
if (s[1] == 'B' && ret[tot] != ret[tot - 1]) return;
if (s[2] == 'B' && ret[tot] != ret[1]) return;
if (s[1] == 'W' && !(ret[2] != ret[1] || ret[tot] != ret[tot - 1])) return;
if (s[2] == 'W' && !(ret[3] != ret[2] || ret[1] != ret[tot])) return;
printf("%s\n", ret + 1);
exit(0);
return;
}
if (x < 1 || x > n || y < 1 || y > m || vis[x][y]) return;
vis[x][y] = depth;
if (depth == 1) {
for (int i = 0; i <= 3; i++) {
ret[depth] = ch[i];
work(depth + 1, x + dx[i], y + dy[i], 1 * (s[depth] == 'B'));
}
vis[x][y] = 0;
return;
}
if (s[depth] == 'B') {
if (flg == 1 || (depth >= 3 && ret[depth - 2] != ret[depth - 1])) {
vis[x][y] = 0;
return;
}
for (int i = 0; i <= 3; i++) {
if (ch[i] == ret[depth - 1]) continue;
ret[depth] = ch[i];
work(depth + 1, x + dx[i], y + dy[i], 1);
}
vis[x][y] = 0;
return;
}
if (s[depth] == 'W') {
if (flg == 2) {
vis[x][y] = 0;
return;
}
for (int i = 0; i <= 3; i++) {
if (ch[i] != ret[depth - 1]) continue;
ret[depth] = ch[i];
work(depth + 1, x + dx[i], y + dy[i], 2 * (depth >= 3 && ret[depth - 1] == ret[depth - 2]));
}
vis[x][y] = 0;
return;
}
if (s[depth] == '.') {
if (flg == 0) {
for (int i = 0; i <= 3; i++) {
ret[depth] = ch[i];
work(depth + 1, x + dx[i], y + dy[i], 0);
}
} else if (flg == 1) {
for (int i = 0; i <= 3; i++) {
if (ch[i] != ret[depth - 1]) continue;
ret[depth] = ch[i];
work(depth + 1, x + dx[i], y + dy[i], 0);
}
} else {
for (int i = 0; i <= 3; i++) {
if (ch[i] == ret[depth - 1]) continue;
ret[depth] = ch[i];
work(depth + 1, x + dx[i], y + dy[i], 0);
}
}
vis[x][y] = 0;
return;
}
}
int main() {
scanf("%d%d%d", &tot, &n, &m);
scanf("\n%s", s + 1);
scanf("%d%d", &sx, &sy);
work(1, sx, sy, 0);
puts("impossible");
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3752kb
input:
16 5 6 B.B.B.BW.WB..WB. 3 1
output:
EENNEESSSSWWWWNN
result:
ok single line: 'EENNEESSSSWWWWNN'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
6 5 5 W..B.B 3 3
output:
impossible
result:
ok single line: 'impossible'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
8 5 5 B.B.B.B. 5 5
output:
NNWWSSEE
result:
ok single line: 'NNWWSSEE'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
8 10 10 B.BWBWB. 2 10
output:
SSWWNNEE
result:
ok single line: 'SSWWNNEE'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
10 5 10 W.B.BW.B.B 4 4
output:
EENNWWWSSE
result:
ok single line: 'EENNWWWSSE'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
10 10 10 B.B.B.B.B. 7 3
output:
impossible
result:
ok single line: 'impossible'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
12 10 10 B.B.B.B.B.B. 10 1
output:
impossible
result:
ok single line: 'impossible'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
16 15 15 B.B.B.B.B.B.B.B. 4 4
output:
impossible
result:
ok single line: 'impossible'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
24 20 20 B.B.B.B.B.B.B.B.B.B.B.B. 1 8
output:
EESSEESSWWSSWWNNWWNNEENN
result:
ok single line: 'EESSEESSWWSSWWNNWWNNEENN'
Test #10:
score: 0
Accepted
time: 9ms
memory: 3576kb
input:
60 50 50 B.B.B.B.B.B.BWB.B.B.B..B.B.B.B.BWB.B.B.B.B.B.B.B.B.B.B.B.B.. 10 10
output:
impossible
result:
ok single line: 'impossible'
Test #11:
score: 0
Accepted
time: 23ms
memory: 3580kb
input:
60 50 50 WW.B.WBWB.BWB.B.B.B.B.B.B.B.B...B.B.B..B.B.B.B..B.B.B.B..B.B 38 20
output:
impossible
result:
ok single line: 'impossible'
Test #12:
score: 0
Accepted
time: 6ms
memory: 3700kb
input:
60 50 50 BWBWBWB.W..B.B..WWB.WB.BWB.B..B..B.B.B.B..B.B.B..B.B.B.B.B.. 5 13
output:
impossible
result:
ok single line: 'impossible'
Test #13:
score: 0
Accepted
time: 3ms
memory: 3836kb
input:
60 50 50 B.W...W.W.B.B.WB.WB.B.B.B..B.B.B.B.B..B.B..B.B.BWWBW.B.WBWB. 31 21
output:
EEENNNNEEENNEEENNNEESSEESSSWWSSWWSSWWWSSWWWSSWWNNNWWWNNNEESS
result:
ok single line: 'EEENNNNEEENNEEENNNEESSEESSSWWSSWWSSWWWSSWWWSSWWNNNWWWNNNEESS'
Test #14:
score: 0
Accepted
time: 1ms
memory: 3844kb
input:
60 50 50 W.B.B..B.B.B....B.B.B.B.B..B.B.B.B..B.BWBWWB.B.WBWB..W.B.BWB 35 20
output:
EENNEEENNEENNNEENNWWNNWWSSSWWNNWWSSSWWSSEEESSWWWSSWWSSSEENNE
result:
ok single line: 'EENNEEENNEENNNEENNWWNNWWSSSWWNNWWSSSWWSSEEESSWWWSSWWSSSEENNE'
Test #15:
score: 0
Accepted
time: 73ms
memory: 3752kb
input:
60 50 50 W.B.BWB..WBWWBWB.BWB.B.B.B.B..B.B.B.B....B.B.B.B.B.B..BWB.BW 8 36
output:
impossible
result:
ok single line: 'impossible'
Test #16:
score: 0
Accepted
time: 74ms
memory: 3836kb
input:
60 50 50 BW.WB.BWB.B.B.B.B...B.B.B.B.B...B.B.B.B.B.B.B.B..B..B.B.BWBW 13 29
output:
impossible
result:
ok single line: 'impossible'
Test #17:
score: 0
Accepted
time: 38ms
memory: 3684kb
input:
60 50 50 B.B..B.B.B.B.B..WB.B.B.BW.W.BWB.BW.BWWB.B..B...B.B.B.B.B.B.. 16 35
output:
impossible
result:
ok single line: 'impossible'
Test #18:
score: 0
Accepted
time: 54ms
memory: 3744kb
input:
60 50 50 B.B...B..B..B..B..B.BW.WBWBWB..WBWBWB.B.B..B.B.B.B.B..B.B.B. 33 30
output:
impossible
result:
ok single line: 'impossible'
Test #19:
score: 0
Accepted
time: 68ms
memory: 3620kb
input:
60 50 50 B...B.B.B..B.BWBWBWBWBWB.BWBWBW.WWB.B.B...B.B.B.B...B.B.B... 30 32
output:
impossible
result:
ok single line: 'impossible'
Test #20:
score: 0
Accepted
time: 94ms
memory: 3620kb
input:
60 50 50 WBWB.B.B.B...B.B..B..B...B.B.B.WBWB.WBWB...BWB..B.BWW.WB...B 33 12
output:
impossible
result:
ok single line: 'impossible'
Test #21:
score: 0
Accepted
time: 159ms
memory: 3836kb
input:
60 50 50 BW.B.B.B.B...B.B...BWB.W.WWB.B...B..B.B...B.B..WBWB..WB.B.WW 15 14
output:
impossible
result:
ok single line: 'impossible'
Test #22:
score: 0
Accepted
time: 219ms
memory: 3616kb
input:
60 50 50 B.BW.W.WWB....B..B..B.B.B...B...B.B.B.B.B.B.B..BWB.WB.BWB.WW 23 13
output:
impossible
result:
ok single line: 'impossible'
Test #23:
score: 0
Accepted
time: 458ms
memory: 3812kb
input:
60 50 50 BWWBWBWWBWB.B.B..B.B....B....B...B.B...B..B.B.B.BW.B.BW.BWW. 15 38
output:
impossible
result:
ok single line: 'impossible'
Test #24:
score: 0
Accepted
time: 457ms
memory: 3836kb
input:
60 50 50 BWWBWBWWBWB.B.B..B.B....B....B...B.B...B..B.B.B.BW.B.BW.BWWB 15 38
output:
impossible
result:
ok single line: 'impossible'
Test #25:
score: 0
Accepted
time: 220ms
memory: 3832kb
input:
60 50 50 W.BW.W.WWB....B..B..B.B.B...B...B.B.B.B.B.B.B..BWB.WB.BWB.WW 23 13
output:
impossible
result:
ok single line: 'impossible'
Test #26:
score: 0
Accepted
time: 175ms
memory: 3840kb
input:
60 50 50 B.WB.B.BWBW.WB....B.B.B.B.B.B..B.B.B.B.B....B.B.B.B..WBWBWW. 28 5
output:
impossible
result:
ok single line: 'impossible'
Test #27:
score: 0
Accepted
time: 708ms
memory: 3700kb
input:
60 50 50 B.B.WB..B...B..B.B.B...B.....B.B.B....BWWBW.BW.WBWBWB.W.BWB. 46 24
output:
impossible
result:
ok single line: 'impossible'
Test #28:
score: 0
Accepted
time: 416ms
memory: 3580kb
input:
60 50 50 B.B.B.B...B.B..B.B.B..B.B.....BWB.WBWBWW.W..BWB.B...WW.BWB.. 18 23
output:
impossible
result:
ok single line: 'impossible'
Test #29:
score: 0
Accepted
time: 16ms
memory: 3828kb
input:
60 50 50 WW.B.BWWBWWBWBW.WB.B.B.B.B...B.B.B....B..B.B.B.B..B...B.B... 3 5
output:
impossible
result:
ok single line: 'impossible'
Test #30:
score: 0
Accepted
time: 35ms
memory: 3832kb
input:
60 50 50 WWB.B.B..BWB.BW.W..B.WB..BWB...B.B..B.B.B..B.B.B.B.B..B.B.B. 6 36
output:
impossible
result:
ok single line: 'impossible'