QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#719082#8981. Kangaroo PuzzleSuhy#TL 1ms3820kbC++143.4kb2024-11-06 22:22:322024-11-06 22:22:39

Judging History

你现在查看的是最新测评结果

  • [2024-11-06 22:22:39]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3820kb
  • [2024-11-06 22:22:32]
  • 提交

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...

result: