QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#244282#7699. PearlsSolitaryDreamWA 457ms3776kbC++142.0kb2023-11-08 22:43:242023-11-08 22:43:24

Judging History

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

  • [2023-11-08 22:43:24]
  • 评测
  • 测评结果:WA
  • 用时:457ms
  • 内存:3776kb
  • [2023-11-08 22:43:24]
  • 提交

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) {
    // int d1 = GetDir(px[ps], py[ps], px[(ps + 1) % k], py[(ps + 1) % k]);
    // int d2 = GetDir(px[ps], py[ps], px[(ps - 1 + k) % k], py[(ps - 1 + k) % k]);
    if (s[ps] == '.') return !ty[ps];
    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 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(x, y, sx, sy) - 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]) {
            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: 0ms
memory: 3624kb

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

input:

6 5 5
W..B.B
3 3

output:

impossible

result:

ok single line: 'impossible'

Test #3:

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

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

input:

8 10 10
B.BWBWB.
2 10

output:

SSWWNNEE

result:

ok single line: 'SSWWNNEE'

Test #5:

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

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

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

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

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

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: 164ms
memory: 3756kb

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: 457ms
memory: 3628kb

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: 0ms
memory: 3484kb

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: -100
Wrong Answer
time: 0ms
memory: 3536kb

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:

impossible

result:

wrong answer 1st lines differ - expected: 'EEENNNNEEENNEEENNNEESSEESSSWWSSWWSSWWWSSWWWSSWWNNNWWWNNNEESS', found: 'impossible'