QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#726366 | #8981. Kangaroo Puzzle | yell | WA | 1ms | 3916kb | C++20 | 1.7kb | 2024-11-08 23:22:26 | 2024-11-08 23:22:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
constexpr int mod = 1e9 + 7;
void solve() {
int n, m;
cin >> n >> m;
vector<string> s(n);
int sx = 0, sy = 0;
for (int i = 0; i < n; i++) {
cin >> s[i];
for (int j = 0; j < m; j++) {
if (s[i][j] == '1') {
sx = i;
sy = j;
}
}
}
queue<tuple<string, int, int>> q;
vector vis(n, vector(m, 0));
q.emplace("", sx, sy);
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
string d = "DURL";
vector<string> v;
while (!q.empty()) {
auto [str, x, y] = q.front();
q.pop();
if (vis[x][y]) continue;
vis[x][y] = 1;
v.push_back(str);
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m || s[nx][ny] == '0' || vis[nx][ny]) {
continue;
}
q.emplace(str + d[i], nx, ny);
}
}
map<int, vector<string>, greater<>> mp;
for (int i = v.size() - 1; i >= 0; i--) {
auto &x = v[i];
reverse(x.begin(), x.end());
for (auto c : d) {
mp[count(x.begin(), x.end(), c)].push_back(x);
}
}
LL sum = 0;
for (auto [k, v] : mp) {
sum += v.size();
assert(sum <= 50000);
for (auto x : v) {
cout << x;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3632kb
input:
4 4 1111 1001 1001 1110
output:
UULLLDDDRRUULLLDDDRRULLLDDDRRULLLDDDRRLLLDDDRRLLLDDDRRLLDDDRRLDDDRRDDDRRUULLLDDDRRUULLLDDDRRULLLDDDRRLLLDDDRRLLDDDRRLLDDDRRLDDDRRDDDRRDDRRDDRRDRRRRULLLDDDRRLDDDRRDRRRLLLDDDRRLLDDDRRLDDDRRDDDRRDDDRRDDRRDDRRDRRDRRRRRRRRRRR
result:
ok AC
Test #2:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
2 15 111111111111111 101010101010101
output:
URRRRRRRRRRRRRRDRRRRRRRRRRRRRRDRRRRRRRRRRRRRDURRRRRRRRRRRRDRRRRRRRRRRRRDRRRRRRRRRRRDURRRRRRRRRRDRRRRRRRRRRDRRRRRRRRRDURRRRRRRRDRRRRRRRRDRRRRRRRDURRRRRRDRRRRRRDRRRRRDURRRRDRRRRDRRRDURRDRRDURRRRRRRRRRRRRRDURRRRRRRRRRRRRRDRRRRRRRRRRRRRRDRRRRRRRRRRRRRDURRRRRRRRRRRRDURRRRRRRRRRRRDRRRRRRRRRRRRDRRRRRRRRRRR...
result:
ok AC
Test #3:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
1 2 11
output:
RRRR
result:
ok AC
Test #4:
score: 0
Accepted
time: 1ms
memory: 3696kb
input:
20 20 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000010000 00000000000000010100 00000000000000111110 11001100000001101001 01110100111001000111 10011111101111001101 11110100110101001001 01000000001101011101 00000000000011010000 01000000000110010000 11100000001010110000 ...
output:
DDLDLDDDDDLDDDDLLDLDDDRRDRRRURRRRRURRDRRRDDDLDDDDLLDLDDDRRRDRRDRRRRRURRDRRRDDDLDDDDLLDLDDDRRRRRURRRRRURRDRRRDDDLDDDDLLDLDDDRRDLLLDLDDDDDLDDDDLLDLDDDRRDLDLDDDDDLDDDDLLDLDDDRRRDRRDRRRRRURRDRRRDDDLDDDDLLDLDDDRRURRURRRRRURRDRRRDDDLDDDDLLDLDDDRRDRRDRRRRRURRDRRRDDDLDDDDLLDLDDDRRDRRDRRRRRURRDRRRDDDLDDDDLLD...
result:
ok AC
Test #5:
score: 0
Accepted
time: 1ms
memory: 3736kb
input:
20 20 10101010000000111100 11111110000000100111 00101000000000000101 11101100000000001011 01000101100000001101 01001110111010111011 00111011001011101010 00101001111001001111 11001011000111011010 01010110000000110100 11110010000101011100 10011111101101110011 10101000100111000110 11100111111100111011 ...
output:
URRRDRRDDDDLDDLLDLDDDLLDLLDDRDRDDLDLLDDRRRRDDRDDRDRDDLDDDRRDDRRRDRDRDDLDLLDRRRDRRDDDDLDDLLDLDDDLLDLLDDRDRDDLDLLDRRDRRDDDDLDDLLDLDDDLLDLLDDRDRDDLDLLDDLLDDRDDRDRDDLDDDRRDDRRRDRDRDDLDLLDDRRDDRDDRDRDDLDDDRRDDRRRDRDRDDLDLLDRDRRDDDDLDDLLDLDDDLLDLLDDRDRDDLDLLDDRRDDDDLDDLLDLDDDLLDLLDDRDRDDLDLLDDDDRDDRDRDDLD...
result:
ok AC
Test #6:
score: 0
Accepted
time: 1ms
memory: 3916kb
input:
20 20 11101111101011101010 10110000101100111111 11011111100101001010 10010010110111110111 01101001101101010101 11001111010101011001 01110101110010001111 11010100001110011001 01010111101011100111 10111100100100111101 11001011111101010100 10111010010011010011 10100110111110111110 11101011010101101000 ...
output:
LUURRDRDRRRRRDDLDLLDDDRRRDDRDDRRDDDDDRRDRRURRRRDDUUURRDRDRRRRRDDLDLLDDDRRRDDRDDRRDDDDDRRDRRURRRRDDUURRDRDRRRRRDDLDLLDDDRRRDDRDDRRDDDDDRRDRRURRRRDDURRDRDRRRRRDDLDLLDDDRRRDDRDDRRDDDDDRRDRRURRRRDDRRDRDRRRRRDDLDLLDDDRRRDDRDDRRDDDDDRRDRRURRRRDDRDRDRRRRRDDLDLLDDDRRRDDRDDRRDDDDDRRDRRURRRRDDLUURRDRDRRRRRDDL...
result:
ok AC
Test #7:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
10 10 1010100000 1111110000 0001010000 0101000000 1111100000 1001000000 1110000000 1011000000 0001100000 0000110000
output:
DRRRDDDLLLDDRRDRDRDRDLDDDLLLDDRRDRDRDRDRDDDLLLDDRRDRDRDRDRRRDDDLLLDDRRDRDRDRULLDDDLLLDDRRDRDRDRRRRDDDLLLDDRRDRDRDRRRRDDDLLLDDRRDRDRDRLLDDDLLLDDRRDRDRDRRRDDDLLLDDRRDRDRDRLDDDLLLDDRRDRDRDRRDDDLLLDDRRDRDRDRDDDLLLDDRRDRDRDRRRDDDLLLDDRRDRDRDRDDLLLDDRRDRDRDRDRDDDLLLDDRRDRDRDRRDDDLLLDDRRDRDRDRDLLLDDRRDRDRD...
result:
ok AC
Test #8:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
12 12 000000011101 000011110111 000001010001 000011000011 000010000000 000010000000 000000000000 000000000000 000000000000 000000000000 000000000000 000000000000
output:
RUULLULLDLLDDLDDUULLULLDLLDDLDDULLULLDLLDDLDDDLLULLDLLDDLDDLLULLDLLDDLDDDLLULLDLLDDLDDLULLDLLDDLDDRUULLULLDLLDDLDDUULLULLDLLDDLDDULLULLDLLDDLDDLLULLDLLDDLDDLULLDLLDDLDDULLDLLDDLDDULLDLLDDLDDLLDLLDDLDDLLDLLDDLDDLDLLDDLDDDLLDDLDDLDLLDDLDDULLDDLDDLLDDLDDLDDLDDRDDLDDDDLDDRUULLULLDLLDDLDDUULLULLDLLDDLDDU...
result:
ok AC
Test #9:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
20 20 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000100000000000 00000011110000000000 00000001010000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 ...
output:
RRRDURRDRRDDRDRRRDURRDURRDRRDDRDRDRDDRRRDRRRDURRDRRDRRDDRDDRDRDRDDDD
result:
ok AC
Test #10:
score: 0
Accepted
time: 1ms
memory: 3652kb
input:
20 20 00000000000111111111 00000000000010010100 10000000000001110111 10000000110010010100 11000011010011010001 01000010010101011111 01110111110111110000 11011101011100100011 01000000110000111110 11000000000000101010 01110100100001101101 11011111111000010111 10000010101001111010 11000011000111010010 ...
output:
LUURUUUUURRDRRURRRRDRRURRRDDRRDDRDRDDDLDLLLDDRRRRDRDUURUUUUURRDRRURRRRDRRURRRDDRRDDRDRDDDLDLLLDDRRRRDRDURUUUUURRDRRURRRRDRRURRRDDRRDDRDRDDDLDLLLDDRRRRDRDRUUUUURRDRRURRRRDRRURRRDDRRDDRDRDDDLDLLLDDRRRRDRDDDRDDRRDRRURRRRDRRURRRDDRRDDRDRDDDLDLLLDDRRRRDRDRUUURRDRRURRRRDRRURRRDDRRDDRDRDDDLDLLLDDRRRRDRDDRD...
result:
ok AC
Test #11:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
2 1 1 1
output:
DDDD
result:
ok AC
Test #12:
score: -100
Wrong Answer
time: 1ms
memory: 3740kb
input:
20 20 11111111111111111111 10000000000000000000 11111111111111111111 00000000000000000001 11111111111111111111 10000000000000000000 11111111111111111111 00000000000000000001 11111111111111111111 10000000000000000000 11111111111111111111 00000000000000000001 11111111111111111111 10000000000000000000 ...
output:
LLLLLLLLLLLLLLLLLLLDDRRRRRRRRRRRRRRRRRRRDDLLLLLLLLLLLLLLLLLLLDDRRRRRRRRRRRRRRRRRRRDDLLLLLLLLLLLLLLLLLLLDDRRRRRRRRRRRRRRRRRRRDDLLLLLLLLLLLLLLLLLLLDDRRRRRRRRRRRRRRRRRRRDDLLLLLLLLLLLLLLLLLLLDDDRRURRDRRURRDRRURRDRRURRDRRRLLLLLLLLLLLLLLLLLLLDDRRRRRRRRRRRRRRRRRRRDDLLLLLLLLLLLLLLLLLLLDDRRRRRRRRRRRRRRRRRRRD...
result:
wrong answer Line [name=ans] equals to "LLLLLLLLLLLLLLLLLLLDDRRRRRRRRR...RDRRRDRRRRRRRRRRRRRRRRRRDRDRRRR", doesn't correspond to pattern "[UDLR]{1,50000}"