QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#638854#8981. Kangaroo Puzzlesea_birdWA 57ms3904kbC++202.9kb2024-10-13 17:05:492024-10-13 17:05:49

Judging History

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

  • [2024-11-05 18:07:55]
  • hack成功,自动添加数据
  • (/hack/1130)
  • [2024-10-13 17:05:49]
  • 评测
  • 测评结果:WA
  • 用时:57ms
  • 内存:3904kb
  • [2024-10-13 17:05:49]
  • 提交

answer

#include<bits/stdc++.h>
typedef long long ll;
using pii = std::pair<int, int>;
const int maxn = 100;
int a[maxn][maxn];
int n, m;
int dx[] = { -1, 0, 0, 1};
int dy[] = {0, -1, 1, 0};
char s[] = {'U', 'L', 'R', 'D'};
int flag[maxn][maxn];
std::string ans;
void dfs(pii u, pii fa) {
    int x = u.first, y = u.second;
    flag[x][y] = 1;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 1 or nx > n or ny > m or ny < 1 or a[nx][ny] == 0 or (pii{nx, ny} == fa))continue;
        if (i == 0)ans.push_back('U');
        else if (i == 1)ans.push_back('L');
        else if (i == 2)ans.push_back('R');
        else ans.push_back('D');
        dfs({nx, ny}, u);
        if (i == 0)ans.push_back('D');
        else if (i == 1)ans.push_back('R');
        else if (i == 2)ans.push_back('L');
        else ans.push_back('U');
    }
}
pii get(int x, int y) {
    for (auto c : ans) {
        int i = 0;
        if (c == 'L')i = 1;
        else if (c == 'R')i = 2;
        else if (c == 'D')i = 3;
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 1 or nx > n or ny > m or ny < 1)continue;
        if (a[nx][ny] == 1) {
            x = nx;
            y = ny;
        }
    }
    return pii{x, y};
}
int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0), std::cout.tie(0);
    std::cin >> n >> m;
    int num = 0;
    std::vector<pii>arr;
    for (int i = 1; i <= n; i++) {
        std::string s;
        std::cin >> s;
        for (int j = 1; j <= m; j++) {
            a[i][j] = s[j - 1] - '0';
            if (a[i][j] == 1)num++;
            if (a[i][j] == 1) {
                arr.push_back({i, j});
            }
        }
    }
    // std::cout << num << "\n";
    std::string res;
    pii goal;
    int mx = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j] == 1) {
                dfs({i, j}, { -1, -1});
                int cnt = 0;
                goal = get(i, j);
                for (int k = 0; k < (int)arr.size(); k++) {
                    if (goal == get(arr[k].first, arr[k].second))cnt++;
                }
                if (cnt > mx) {
                    res = ans;
                }
                memset(flag, 0, sizeof(flag));
                ans.clear();
            }
        }
    }
    std::cout << res << "\n";
    return 0;
}
// 00000000000111111111
// 00000000000010010100
// 10000000000001110111
// 10000000110010010100
// 11000011010011010001
// 01000010010101011111
// 01110111110111110000
// 11011101011100100011
// 01000000110000111110
// 11000000000000101010
// 01110100100001101101
// 11011111111000010111
// 10000010101001111010
// 11000011000111010010
// 00000000000000010111
// 00000000000111111100
// 00000000000000100000
// 00000000000001111110
// 00000000000000100011
// 00000000000000111001

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3640kb

input:

4 4
1111
1001
1001
1110

output:

LLUUURRRDDUULLLDDDRR

result:

ok AC

Test #2:

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

input:

2 15
111111111111111
101010101010101

output:

ULLLLLLLLLLLLLLDURRDURRDURRDURRDURRDURRDURRD

result:

ok AC

Test #3:

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

input:

1 2
11

output:

LR

result:

ok AC

Test #4:

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

input:

2 1
0
1

output:



result:

ok AC

Test #5:

score: 0
Accepted
time: 15ms
memory: 3904kb

input:

20 20
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000010000
00000000000000010100
00000000000000111110
11001100000001101001
01110100111001000111
10011111101111001101
11110100110101001001
01000000001101011101
00000000000011010000
01000000000110010000
11100000001010110000
...

output:

LLUUULUDLRRRUUUDLRDRRUUUURUUUUURURUUDDRRUDRLLDULLDLDDLLLULLDLLLUULRDDLLULLULRDRRDDLLLUDRDURRURRDURRRDRLUURRDRDDLRUURRDDDLDLRDDRLDDRRURUUUUURUURURRUDDDDUUULLDLDDRLLDDDLRDDRRDRRLLULLLDLLULLDLDDDLLLUUDLLULULULUUUDLRRLDDLDDDRRLDULUUURRDRDRDRRDRRRRR

result:

ok AC

Test #6:

score: -100
Wrong Answer
time: 57ms
memory: 3904kb

input:

20 20
10101010000000111100
11111110000000100111
00101000000000000101
11101100000000001011
01000101100000001101
01001110111010111011
00111011001011101010
00101001111001001111
11001011000111011010
01010110000000110100
11110010000101011100
10011111101101110011
10101000100111000110
11100111111100111011
...

output:

UUUULRDDDLLDLRURRRRURUULULUUUUDLRDRRUUDRRUUURUUUUUDRLDLLDLLUDRDDLLRRUURURRDDRRUURUUUULLULLLDURRRDDURRDDLRDDLDDRLDULLDLDLRDRRUDLLDLLDLLDLLLUULLUUURUULULUULUUUDLLUDLLUDRRDDLLRDDUURUURRRRUDLLDDRDDLDLLDURRDDUUURRDRDRRRUULLULRDRRDDLLLDLDLRDDLLLUUDLLUULRDDLDDDRRUDLLDDRRRDDLDLLUDDURRURRRDRLDLLRRUULLUULLDUL...

result:

wrong answer WA