QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#322038#7699. PearlsishmealAC ✓821ms3764kbC++232.0kb2024-02-06 04:50:172024-02-06 04:50:17

Judging History

你现在查看的是最新测评结果

  • [2024-02-06 04:50:17]
  • 评测
  • 测评结果:AC
  • 用时:821ms
  • 内存:3764kb
  • [2024-02-06 04:50:17]
  • 提交

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'