QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#719082 | #8981. Kangaroo Puzzle | Suhy# | TL | 1ms | 3820kb | C++14 | 3.4kb | 2024-11-06 22:22:32 | 2024-11-06 22:22:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int n,m,i,j,t;
int a[22][22];//0:wall 1:empty 2:kangroo
int vis[22][22];
int s[486],p,x,y;
bool check(){
int r=0;
for(i=1;i<=n;++i)
for(j=1;j<=m;++j)if(a[i][j]==2)++r;
if(r==1)return 0;
return 1;
}
void play(int w){
int i,j;
bool b;
if(w==0){//up
putchar('U');
for(i=1;i<=m;++i){
b=0;//if came
for(j=n;j;--j){
if(a[j][i]==1){
if(b)a[j][i]=2;
b=0;
}else if(a[j][i]==2){
if(b)a[j][i]=2;
else if(a[j-1][i])a[j][i]=1;
b=1;
}else b=0;
}
}
}
if(w==1){//down
putchar('D');
for(i=1;i<=m;++i){
b=0;//if came
for(j=1;j<=n;++j){
if(a[j][i]==1){
if(b)a[j][i]=2;
b=0;
}else if(a[j][i]==2){
if(b)a[j][i]=2;
else if(a[j+1][i])a[j][i]=1;
b=1;
}else b=0;
}
}
}
if(w==2){//left
putchar('L');
for(i=1;i<=n;++i){
b=0;//if came
for(j=m;j;--j){
if(a[i][j]==1){
if(b)a[i][j]=2;
b=0;
}else if(a[i][j]==2){
if(b)a[i][j]=2;
else if(a[i][j-1])a[i][j]=1;
b=1;
}else b=0;
}
}
}
if(w==3){//right
putchar('R');
for(i=1;i<=n;++i){
b=0;//if came
for(j=1;j<=m;++j){
if(a[i][j]==1){
if(b)a[i][j]=2;
b=0;
}else if(a[i][j]==2){
if(b)a[i][j]=2;
else if(a[i][j+1])a[i][j]=1;
b=1;
}else b=0;
}
}
}
}
bool K=0;
bool dfs(int i,int j){
if(vis[i][j])return 0;
vis[i][j]=1;
if(!a[i][j])return 0;
if(a[i][j]==2&&K){x=i,y=j;return 1;}
K=1;
s[p++]=0;
if(dfs(i-1,j))return 1;
--p;
s[p++]=1;
if(dfs(i+1,j))return 1;
--p;
s[p++]=2;
if(dfs(i,j-1))return 1;
--p;
s[p++]=3;
if(dfs(i,j+1))return 1;
--p;
return 0;
}
void pt(){
for(int i=1;i<=n;++i,puts(""))
for(int j=1;j<=m;++j)printf("%d ",a[i][j]);
puts("");
}
int main()
{
scanf("%d%d",&n,&m);
for(i=0;i<=n+1;++i)
for(j=0;j<=m+1;++j)a[i][j]=0;
char c=0;
for(i=1;i<=n;++i)
for(j=1;j<=m;++j){
while(c=getchar(),c!='0'&&c!='1');
if(c=='1')a[i][j]=2;
else a[i][j]=0;
}
while(check()){
for(i=1;i<=n;++i)
for(j=1;j<=m;++j)vis[i][j]=0;
for(i=1;i<=n;++i)
for(j=1;j<=m;++j)if(a[i][j]==2)goto end;
end:;
p=0;
K=0;
dfs(i,j);
int l=0;
while(l<p){
if(s[l]==0&&a[x-1][y])--x,s[p++]=s[l];
if(s[l]==1&&a[x+1][y])++x,s[p++]=s[l];
if(s[l]==2&&a[x][y-1])--y,s[p++]=s[l];
if(s[l]==3&&a[x][y+1])++y,s[p++]=s[l];
if(p>l+2&&(s[p-1]^s[p-2]==1))p-=2;
play(s[l++]);
}
}return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3664kb
input:
4 4 1111 1001 1001 1110
output:
DDDLDDDLDDDUULLLDDD
result:
ok AC
Test #2:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
2 15 111111111111111 101010101010101
output:
DLDURRRRRRRRRRRRRR
result:
ok AC
Test #3:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
1 2 11
output:
R
result:
ok AC
Test #4:
score: 0
Accepted
time: 1ms
memory: 3744kb
input:
20 20 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000010000 00000000000000010100 00000000000000111110 11001100000001101001 01110100111001000111 10011111101111001101 11110100110101001001 01000000001101011101 00000000000011010000 01000000000110010000 11100000001010110000 ...
output:
DDLDLDRDRRULLDDDDDRDDLDDDDDDDDDRRDDLLLDLRDURRRRRURRDRRLLULLLLLLDLLLLLDLULLDLLLLLDLRRRURRRRRURRDRRRDDDUUULLDLDDLDDDDDLDLLUURUURRDDDLDDDDDRDLULLDLDDDLLLUUDLLDLDDDRDRDRRDRRRRR
result:
ok AC
Test #5:
score: -100
Time Limit Exceeded
input:
20 20 10101010000000111100 11111110000000100111 00101000000000000101 11101100000000001011 01000101100000001101 01001110111010111011 00111011001011101010 00101001111001001111 11001011000111011010 01010110000000110100 11110010000101011100 10011111101101110011 10101000100111000110 11100111111100111011 ...
output:
DLDLDRRDDURRRDDDDDURRDDDDUURLDDDUURLDDDUURLDDDUURLDDDUURLDDDUURLDDDUURLDDDUURLDDDUURLDDDUURLDDDUURLDDDUURLDDDUURLDDDUURLDDDUURLDDDUURLDDDUURLDDDUURLDDDUURLDDDUURLDDDUURLDDDUURLDDDUURLDDDUURLDDDUURLDDDUURLDDDUURLDDDUURLDDDUURLDDDUURLDDDUURLDDDUURLDDDUURLDDDUURLDDDUURLDDDUURLDDDUURLDDDUURLDDDUURLDDDUU...