QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#718273#8981. Kangaroo PuzzleKobicGendWA 1ms3904kbC++232.2kb2024-11-06 20:08:482024-11-06 20:08:49

Judging History

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

  • [2024-11-06 20:08:49]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3904kb
  • [2024-11-06 20:08:48]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
using i64 = long long;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define multi int _;cin>>_;while(_--)
#define int long long
#define pb push_back
#define eb emplace_back
mt19937_64 mrand(chrono::steady_clock().now().time_since_epoch().count());
int rnd(int l,int r){ return mrand() % (r - l + 1) + l;}

signed main()
{  
#ifdef localfreopen
    // freopen("1.in","r",stdin);
#endif
    fastio
    std::cout << std::fixed << std::setprecision(10);
    int n, m;
    std::cin >> n >> m;

    std::vector is(n + 1, std::vector<int> (m + 2));
    for (int i = 1; i <= n; i++) {
        std::string s;
        std::cin >> s;
        for (int j = 0; j < m; j++) {
            is[i][j + 1] = s[j] - '0';
        }
    }

    std::string ans;

    std::vector<std::pair<int, int>> D = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    std::vector<char> target = {'R', 'L', 'D', 'U'};
    auto dfs = [&](auto self, int x, int y, int fx, int fy, int rx, int ry, std::string s)->void{
        int cnt = 0;
        for (int k = 0; k < 4; k++) {
            auto [dx, dy] = D[k];
            int nx = x + dx, ny = y + dy;
            if (nx < 1 || nx > n || ny < 1 || ny > m || is[nx][ny] == 0 || (nx == fx && ny == fy)) continue;
            cnt++;
            self(self, nx, ny, x, y, rx, ry, s + target[k]);
        }
        if (cnt == 0) {
            ans += s;
        }
    };


    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (is[i][j] == 1) {
                int cnt = 0;
                for (auto [dx, dy] : D) {
                    int nx = i + dx, ny = j + dy;
                    if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && is[nx][ny] == 1) {
                        cnt++;
                    }
                }
                if (cnt == 1) {
                    dfs(dfs, i, j, 0, 0, i, j, "");                    
                }
            }
        }
    }
    std::cout << ans << "\n";


    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4 4
1111
1001
1001
1110

output:

UULLLDDDRRLLUUURRRDD

result:

ok AC

Test #2:

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

input:

2 15
111111111111111
101010101010101

output:

URRRRRRRRRRRRRRDURRRRRRRRRRRRDURRRRRRRRRRDURRRRRRRRDURRRRRRDURRRRDURRDURRRRRRRRRRRRDURRRRRRRRRRDURRRRRRRRDURRRRRRDURRRRDURRDULLDURRRRRRRRRRDURRRRRRRRDURRRRRRDURRRRDURRDULLLLDULLDURRRRRRRRDURRRRRRDURRRRDURRDULLLLLLDULLLLDULLDURRRRRRDURRRRDURRDULLLLLLLLDULLLLLLDULLLLDULLDURRRRDURRDULLLLLLLLLLDULLLLLLL...

result:

ok AC

Test #3:

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

input:

1 2
11

output:

RL

result:

ok AC

Test #4:

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

input:

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

output:

DDRRRDDRRUDDRDDDLDLDDLLLULLDLLLLLDLLLUDDLDLDDLLLULLDLLLLLDLLDDDLDLDDLLLULLDLLLLLULLULDDLDLDDLLLULLDLLLDDDLDLDDLLLULLDLLLUULDDLDLDDLLLULLDDRDDLDLDDLLDDLDDLDLDDDDDLDLDDLDLDDDDDLDDDRDDLDLDDDDDLDDDDLLDLLLDDLDLDDDDDLDDDDLLDLLUDDLDLDDDDDLDDDDLLDLDDDRRDDLDLDDDDDLDDDDLLDLDDDLLLULLULULULLDDDRRDDLDLDDDDDLDDDD...

result:

ok AC

Test #5:

score: -100
Wrong Answer
time: 1ms
memory: 3756kb

input:

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

output:

DRRRRRRUDRRRRDDRDDRDRDRRRUULLULDRRRRDDRDDRDRDDLDLDRRRRDDRDDRDRDDLDDDRRDDRRRDRDRDRRRRRURDRRRRDDRDDRDRDDLDDDRRDDRRRDRDRDRRRRRUUURDRRRRDDRDDRDRDDLDDDRRDDRRRDRDRDRRRRRUUUULDRRRRDDRDDRDRDDLDDDRRDDRRRDRDRDRRRRRUUUUURDRRRRDDRDDRDRDDLDDDRRDDRRRDRDRDRRRUUULLDDRRRRDDRDDRDRDDLDDDRRDDRRRDRDRDRRDDRRRRDDRDDRDRDDL...

result:

wrong answer Line [name=ans] equals to "DRRRRRRUDRRRRDDRDDRDRDRRRUULLU...LULUUULURRURUULULUUUUULLDLUUUUL", doesn't correspond to pattern "[UDLR]{1,50000}"