QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#718273 | #8981. Kangaroo Puzzle | KobicGend | WA | 1ms | 3904kb | C++23 | 2.2kb | 2024-11-06 20:08:48 | 2024-11-06 20:08:49 |
Judging History
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}"