QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#244314#7699. PearlsSolitaryDreamAC ✓4336ms3532kbC++172.0kb2023-11-08 23:07:162023-11-08 23:07:17

Judging History

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

  • [2023-11-08 23:07:17]
  • 评测
  • 测评结果:AC
  • 用时:4336ms
  • 内存:3532kb
  • [2023-11-08 23:07:16]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 65;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
string d2ch = "NESW";
vector<int> order = {1, 0, 2, 3};
int k, n, m;
string s;
int sx, sy;

string ans;
int ty[N];
int vis[N][N], px[N], py[N];
inline int GetDir(int x, int y, int u, int v) {
    if (x == u) return v < y ? 3 : 1;
    return u < x ? 0 : 2;
}
inline int Check(int ps) {
    if (s[ps] == '.') return 1;
    if (s[ps] == 'W') return !ty[ps] && (ty[(ps + 1) % k] || ty[(ps + k - 1) % k]);
    return ty[ps] && !ty[(ps + 1) % k] && !ty[(ps + k - 1) % k];
}
inline int dis(int x, int y, int u, int v) {
    return abs(x - u) + abs(y - v);
}
inline void Dfs(int x, int y, int ps) {
    px[ps] = x; py[ps] = y;
    if (ps == k - 1) {
        // cerr << ans << endl;
        // cerr << x << ' ' << y << endl;
        if (abs(x - sx) + abs(y - sy) != 1) return;
        ans[ps] = d2ch[GetDir(x, y, sx, sy)];
        ty[ps] = ((GetDir(sx, sy, x, y) - GetDir(x, y, px[ps - 1], py[ps - 1]) + 4) % 4 & 1);
        ty[0] = ((GetDir(px[0], py[0], px[1], py[1]) - GetDir(px[0], px[0], x, y) + 4) % 4 & 1);
        if (Check(ps) && Check(ps - 1) && Check(0) && Check(1)) {
            cout << ans << endl;
            exit(0);
        }
        return;
    }
    vis[x][y] = 1;
    for (auto d : order) {
        int nx = x + dx[d], ny = y + dy[d];
        if (nx > 0 && ny > 0 && nx <= n && ny <= m && !vis[nx][ny] && dis(nx, ny, sx, sy) <= k - ps) {
            ans[ps] = d2ch[d];
            if (ps >= 1) ty[ps] = (d - GetDir(x, y, px[ps - 1], py[ps - 1]) + 4) % 4 & 1;   
            if (ps >= 3 && !Check(ps - 1)) continue;
            Dfs(nx, ny, ps + 1);
        }
    }
    vis[x][y] = 0;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> k >> n >> m;
    cin >> s;
    cin >> sx >> sy;
    ans.resize(k);
    Dfs(sx, sy, 0);
    cout << "impossible\n";
    return 0;
} 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3396kb

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: 3488kb

input:

6 5 5
W..B.B
3 3

output:

impossible

result:

ok single line: 'impossible'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3412kb

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: 3416kb

input:

8 10 10
B.BWBWB.
2 10

output:

SSWWNNEE

result:

ok single line: 'SSWWNNEE'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3472kb

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: 3520kb

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: 3392kb

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: 1ms
memory: 3400kb

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: 1ms
memory: 3396kb

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: 17ms
memory: 3440kb

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: 136ms
memory: 3472kb

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: 13ms
memory: 3512kb

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: 6ms
memory: 3444kb

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: 2ms
memory: 3520kb

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: 165ms
memory: 3428kb

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: 572ms
memory: 3528kb

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: 95ms
memory: 3432kb

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: 120ms
memory: 3436kb

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: 535ms
memory: 3520kb

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: 381ms
memory: 3500kb

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: 1211ms
memory: 3516kb

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: 522ms
memory: 3420kb

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: 4336ms
memory: 3532kb

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: 4315ms
memory: 3468kb

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: 509ms
memory: 3472kb

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: 1300ms
memory: 3520kb

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: 2028ms
memory: 3500kb

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: 1333ms
memory: 3400kb

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: 153ms
memory: 3396kb

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: 87ms
memory: 3432kb

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'