QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #638462 | #8981. Kangaroo Puzzle | sea_bird | WA | 26ms | 3856kb | C++14 | 2.2kb | 2024-10-13 15:58:16 | 2024-10-13 15:58:17 |
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(a[nx][ny] == 0 or flag[nx][ny] or nx < 1 or nx > n or ny > m or ny < 1)continue;
ans.push_back(s[i]);
dfs({nx,ny},u);
ans.push_back(s[3 - i]);
}
}
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::string res;
pii goal;
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 == num and ans.size() < (int)5e4){
std::cout << ans << "\n";
return 0;
}
else{
memset(flag,0,sizeof(flag));
ans.clear();
}
}
}
}
for(int i = 10;i<=n;i++){
for(int j = 1;j<=m;j++){
std::cout << a[i][j];
}
std::cout << "\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3568kb
input:
4 4 1111 1001 1001 1110
output:
RRRDDUULLLDDDRRLLUUU
result:
ok AC
Test #2:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
2 15 111111111111111 101010101010101
output:
RRRRRRRRRRRRRRDULLDULLDULLDULLDULLDULLDULLDU
result:
ok AC
Test #3:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
1 2 11
output:
RL
result:
ok AC
Test #4:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
2 1 0 1
output:
result:
ok AC
Test #5:
score: 0
Accepted
time: 1ms
memory: 3660kb
input:
20 20 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000010000 00000000000000010100 00000000000000111110 11001100000001101001 01110100111001000111 10011111101111001101 11110100110101001001 01000000001101011101 00000000000011010000 01000000000110010000 11100000001010110000 ...
output:
RDRRDRRUULRDDRRRURRDRRRUURURUUDDRRUDRLLDULLDLDDDDDLDLRDDRLDLLUUDLRDDLLUDLRRDDDLLLUUDLLULULULUUUDLRRLDDLDDDRRLDULUUURRDRDRDRRDRRRRRLLUUURURRDRRURUUUUURUURURRUDDDDUUULLDLDDRLLDDDLRDDRRDRRLLULLLDLLUUUUURUUULLDDLRUULULLDDRLULLLDULLDLLLUDRDURRUULLUL
result:
ok AC
Test #6:
score: 0
Accepted
time: 26ms
memory: 3856kb
input:
20 20 10101010000000111100 11111110000000100111 00101000000000000101 11101100000000001011 01000101100000001101 01001110111010111011 00111011001011101010 00101001111001001111 11001011000111011010 01010110000000110100 11110010000101011100 10011111101101110011 10101000100111000110 11100111111100111011 ...
output:
DLRDRRUUDRRUUURUUUUUDRLDLLDLLUDRDDLLRRUURURRDDRRUURUUUULLULLLDURRRDDURRDDLRDDLDDRLDULLDLDLRDRRUDLLDLLDLLDLLLUULLUUURUULULUULUUUDLLUDLLUDRRDDLLRDDUURUURRRRUDLLDDRDDLDLLDURRDDUUURRDRDRRRUULLULRDRRDDLLLDLDLRDDLLLUUDLLUULRDDLDDDRRUDLLDDRRRDDLDLLUDDURRURRRDRLDLLRRUULLUULLDULUUUUURRRDRDURRRRDDLLLDLRDRRDRL...
result:
ok AC
Test #7:
score: 0
Accepted
time: 2ms
memory: 3604kb
input:
20 20 11101111101011101010 10110000101100111111 11011111100101001010 10010010110111110111 01101001101101010101 11001111010101011001 01110101110010001111 11010100001110011001 01010111101011100111 10111100100100111101 11001011111101010100 10111010010011010011 10100110111110111110 11101011010101101000 ...
output:
RRRRDDLLLLLULULLDDRLDUUURRDRDDURRRDURRDRLDLDLLLUDRDDDRRRDDLLDDLRDRDRLULUUURRRRRUDLLDDLRRRRURUDLDLDDDLLRRRRLLDDRRDRRUUUULUURUUULULLUUDLLDURRDRRDRRRURRUUUUULUUUDLLUDLLULLRRDRRDURRRLDDLDURRDDDLLLULUULLUDLLUULUDRDDDLRDUURRDDUURRDDRDDLRURRRDDDULLDDULLDDDRRRURLDLLDULLDLRDRDRLDLRDRRRUUULRDRLDDRDDLRUULLDULL...
result:
ok AC
Test #8:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
10 10 1010100000 1111110000 0001010000 0101000000 1111100000 1001000000 1110000000 1011000000 0001100000 0000110000
output:
RUDRRUUULUDLLUDRRRRUDRDULLDDDRLDULLLDDRRDRDRDRLULULULLDUUU
result:
ok AC
Test #9:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
12 12 000000011101 000011110111 000001010001 000011000011 000010000000 000010000000 000000000000 000000000000 000000000000 000000000000 000000000000 000000000000
output:
RRDRRUDDDLRUULLULLDLLLRDDLDDUURUURRDUU
result:
ok AC
Test #10:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
20 20 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000100000000000 00000011110000000000 00000001010000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 ...
output:
DLLRDURRDULU
result:
ok AC
Test #11:
score: -100
Wrong Answer
time: 25ms
memory: 3856kb
input:
20 20 00000000000111111111 00000000000010010100 10000000000001110111 10000000110010010100 11000011010011010001 01000010010101011111 01110111110111110000 11011101011100100011 01000000110000111110 11000000000000101010 01110100100001101101 11011111111000010111 10000010101001111010 11000011000111010010 ...
output:
11000000000000101010 01110100100001101101 11011111111000010111 10000010101001111010 11000011000111010010 00000000000000010111 00000000000111111100 00000000000000100000 00000000000001111110 00000000000000100011 00000000000000111001
result:
wrong output format Expected EOF