QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#322026 | #7699. Pearls | ishmeal | WA | 0ms | 3724kb | C++23 | 1.8kb | 2024-02-06 03:28:06 | 2024-02-06 03:28:06 |
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 (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() == 'W' and NESW[d] != ans[0]) return;
cout << ans << '\n';
exit(0);
}
if (grid[rr][cc]) return;
grid[rr][cc] = true;
// cout << rr << ' ' << cc << ' ' << i << endl;
corner |= s[i] == 'B';
forward |= s[i] == 'W';
for (int dd = 0; dd < 4; dd++) {
if (dd == (d+2)%4) continue;
if (forward and dd != d) continue;
if (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, dd!=d);
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,-100,false,false,s.front()=='W');
cout << "impossible\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3608kb
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: 3604kb
input:
6 5 5 W..B.B 3 3
output:
impossible
result:
ok single line: 'impossible'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3656kb
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: 3664kb
input:
8 10 10 B.BWBWB. 2 10
output:
SSWWNNEE
result:
ok single line: 'SSWWNNEE'
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3724kb
input:
10 5 10 W.B.BW.B.B 4 4
output:
impossible
result:
wrong answer 1st lines differ - expected: 'EENNWWWSSE', found: 'impossible'