QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#707231#7781. Sheep Eat WolvesArkhellTL 772ms3868kbC++141.5kb2024-11-03 15:12:342024-11-03 15:12:35

Judging History

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

  • [2024-11-03 15:12:35]
  • 评测
  • 测评结果:TL
  • 用时:772ms
  • 内存:3868kb
  • [2024-11-03 15:12:34]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int x,y,p,q;
int ans=1e9;
int vis[101][101][2];
void dfs(int time,int x1,int y1,int x2,int y2,int pos){
    
    if(time>=vis[x1][y1][pos]&&vis[x1][y1][pos]!=0){
        return;
    }
    if(x1==x&&y1==y&&time>0){
        return;
    }
    vis[x1][y1][pos]=time;
    
   // cout<<time<<' '<<x1<<' '<<y1<<' '<<x2<<' '<<y2<<' '<<pos<<'\n';
    // if(x1==0){
    //     //cout<<time<<' '<<x1<<' '<<y1<<' '<<x2<<' '<<y2<<' '<<pos<<'\n';
    // }
    if(x1==0){

        ans=min(ans,time);
        return;
    }
    if(pos==1){
        for(int i=0;i<=y2;i++){
            for(int j=0;j<=x2;j++){
                if(i+j>p){
                    break;
                }
                if(y2-i-x2+j>q&&x2-j!=0){
                    continue;
                }
                dfs(time+1,x1+j,y1+i,x2-j,y2-i,0);
            }
        }
    }
    else{
         for(int i=0;i<=y1;i++){
            for(int j=0;j<=x1;j++){
                if(i+j>p){
                    break;
                }
                if((y1-i-x1+j>q&&x1-j!=0)||i+j==0){
                    continue;
                }
                dfs(time+1,x1-j,y1-i,x2+j,y2+i,1);
            }
        }
    }
}
void solve(){
    cin>>x>>y>>p>>q;
    //memset(vis,-1,sizeof(vis));
    dfs(0,x,y,0,0,0);
    if(ans==1e9){
        cout<<-1<<'\n';
    }
    else{
        cout<<ans;
    }

} 
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3548kb

input:

4 4 3 1

output:

3

result:

ok 1 number(s): "3"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3668kb

input:

3 5 2 0

output:

5

result:

ok 1 number(s): "5"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3688kb

input:

2 5 1 1

output:

-1

result:

ok 1 number(s): "-1"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3672kb

input:

1 1 1 0

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3672kb

input:

3 3 1 1

output:

7

result:

ok 1 number(s): "7"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

3 3 2 1

output:

3

result:

ok 1 number(s): "3"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3680kb

input:

10 9 1 10

output:

19

result:

ok 1 number(s): "19"

Test #8:

score: 0
Accepted
time: 1ms
memory: 3692kb

input:

15 20 2 5

output:

27

result:

ok 1 number(s): "27"

Test #9:

score: 0
Accepted
time: 6ms
memory: 3708kb

input:

18 40 16 7

output:

5

result:

ok 1 number(s): "5"

Test #10:

score: 0
Accepted
time: 37ms
memory: 3772kb

input:

60 60 8 1

output:

27

result:

ok 1 number(s): "27"

Test #11:

score: 0
Accepted
time: 96ms
memory: 3868kb

input:

60 60 8 4

output:

27

result:

ok 1 number(s): "27"

Test #12:

score: 0
Accepted
time: 251ms
memory: 3796kb

input:

60 60 8 8

output:

25

result:

ok 1 number(s): "25"

Test #13:

score: 0
Accepted
time: 216ms
memory: 3800kb

input:

60 60 16 1

output:

13

result:

ok 1 number(s): "13"

Test #14:

score: 0
Accepted
time: 772ms
memory: 3864kb

input:

60 60 16 8

output:

11

result:

ok 1 number(s): "11"

Test #15:

score: -100
Time Limit Exceeded

input:

60 60 16 16

output:

11

result: