QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#638854 | #8981. Kangaroo Puzzle | sea_bird | WA | 57ms | 3904kb | C++20 | 2.9kb | 2024-10-13 17:05:49 | 2024-10-13 17:05:49 |
Judging History
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
详细
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