QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#322038 | #7699. Pearls | ishmeal | AC ✓ | 821ms | 3764kb | C++23 | 2.0kb | 2024-02-06 04:50:17 | 2024-02-06 04:50:17 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int n, m;
int r, c;
bool grid[50][50];
string ans;
string s;
pair<int,int> dirs[4] {{-1,0},{0,1},{1,0},{0,-1}};
string NESW = "NESW";
void solve(int rr, int cc, int i, int d, bool forward, bool corner, bool was_corner) {
if (min(rr,cc) < 0 or rr >= n or cc >= m) return;
if (i and s[i] == 'B' and was_corner) return;
if ((unsigned)i == s.size()) {
if (r != rr or c != cc) return;
if (s.front() == 'B' and NESW[d] == ans[0]) return;
if (s.front() == 'B' and was_corner) return;
if (s.front() == 'W' and NESW[d] != ans[0]) return;
if (s.front() == 'W' and NESW[d] == ans[1] and NESW[d] == ans[ans.size()-2]) return;
cout << ans << '\n';
exit(0);
}
if (abs(rr-r) + abs(cc-c) > s.size()-i) return;
if (grid[rr][cc]) return;
grid[rr][cc] = true;
// cout << rr << ' ' << cc << ' ' << i << endl;
forward |= s[i] == 'W';
corner |= s[i] == 'B';
for (int dd : {1, 0, 2, 3}) {
if (i and dd == (d+2)%4) continue;
if (i and forward and dd != d) continue;
if (i and corner and dd == d) continue;
auto [dy,dx] = dirs[dd];
ans += NESW[dd];
if (s[i] == 'W')
solve(rr+dy,cc+dx, i+1, dd, false, !was_corner, false);
else if (s[i] == 'B')
solve(rr+dy,cc+dx, i+1, dd, true, false, true);
else
solve(rr+dy,cc+dx, i+1, dd, false, false, dd!=d);
ans.pop_back();
}
grid[rr][cc] = false;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int k; cin >> k >> n >> m;
cin >> s;
cin >> r >> c; r--, c--;
solve(r,c,0,-1,false,false,true);
cout << "impossible\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3652kb
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: 3616kb
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: 3736kb
input:
8 10 10 B.BWBWB. 2 10
output:
SSWWNNEE
result:
ok single line: 'SSWWNNEE'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3616kb
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: 3672kb
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: 3728kb
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: 3740kb
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: 3692kb
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: 12ms
memory: 3624kb
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: 0ms
memory: 3672kb
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: 3ms
memory: 3624kb
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: 4ms
memory: 3764kb
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: 3700kb
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: 92ms
memory: 3680kb
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: 90ms
memory: 3752kb
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: 47ms
memory: 3700kb
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: 69ms
memory: 3700kb
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: 91ms
memory: 3744kb
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: 110ms
memory: 3680kb
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: 192ms
memory: 3680kb
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: 275ms
memory: 3680kb
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: 547ms
memory: 3696kb
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: 548ms
memory: 3696kb
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: 273ms
memory: 3696kb
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: 212ms
memory: 3616kb
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: 821ms
memory: 3620kb
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: 483ms
memory: 3624kb
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: 0ms
memory: 3608kb
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: 44ms
memory: 3620kb
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'