QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#743995#7781. Sheep Eat Wolvesyld#RE 1ms3608kbC++203.1kb2024-11-13 20:32:232024-11-13 20:32:23

Judging History

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

  • [2024-11-13 20:32:23]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3608kb
  • [2024-11-13 20:32:23]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n,m,p,q;
int cnt=0;
int id[105][105][2];
int getid(int x,int y,int op)
{
    if(!id[x][y][op]) id[x][y][op]=++cnt;
    return id[x][y][op];
}
void solve()
{
    cin>>n>>m>>p>>q;
    vector<int> e[n*m*4+1];
    for(int i=0;i<=n;i++)//i j 都是左
    {
        for(int j=0;j<=m;j++)
        {
            // if(j-i>p && i!=0) continue;
            if((m-j)-(n-i)>p && n-i!=0) continue;
            for(int k=0;k<=n;k++)//k l 都是右
            {
                for(int l=0;l<=m;l++)
                {
                    // if(i+k!=n || j+l!=m) continue;
                    // if(l-k>q && l!=0) continue;
                    // if((m-l)-(n-k)>p && n-k!=0) continue;
                    int sheep=k-(n-i),wolf=l-(m-j);//船上羊的数量 狼的数量
                    // if(i==4 && j==4 && k==2 && l==1) cout<<sheep<<' '<<wolf<<endl;
                    if(sheep<0 || wolf<0) continue;
                    if(sheep+wolf>p) continue;
                    if(j-wolf-(i-sheep)>q && i-sheep!=0) continue;
                    // cout<<i<<' '<<j<<' '<<k<<' '<<l<<endl;
                    // if(i==4 && j==4) cout<<k<<' '<<l<<endl;
                    e[getid(i,j,0)].push_back(getid(k,l,1));
                }
            }
        }
    }
    for(int i=0;i<=n;i++)//i j 都是左
    {
        for(int j=0;j<=m;j++)
        {
            // if(j-i>p && i!=0) continue;
            if((m-j)-(n-i)>p && n-i!=0) continue;
            for(int k=0;k<=n;k++)//k l 都是右
            {
                for(int l=0;l<=m;l++)
                {
                    // if(i+k!=n || j+l!=m) continue;
                    // if(l-k>q && l!=0) continue;
                    // if((m-l)-(n-k)>p && n-k!=0) continue;
                    int sheep=k-(n-i),wolf=l-(m-j);//船上羊的数量 狼的数量
                    // if(i==4 && j==4 && k==2 && l==1) cout<<sheep<<' '<<wolf<<endl;
                    if(sheep<0 || wolf<0) continue;
                    if(sheep+wolf>p) continue;
                    if(j-wolf-(i-sheep)>q && i-sheep!=0) continue;
                    // cout<<i<<' '<<j<<' '<<k<<' '<<l<<endl;
                    // if(k==0 && l==3) cout<<i<<' '<<j<<endl;
                    e[getid(i,j,1)].push_back(getid(k,l,0));
                }
            }
        }
    }
    queue<int> q;
    q.push(getid(n,m,0));
    vector<int> dis(n*m*4+1);
    dis[getid(n,m,0)]=1;
    while(q.size())
    {
        auto u=q.front();q.pop();
        // cout<<x<<' '<<y<<' '<<op<<endl;
        // cout<<u<<endl;
        for(auto v:e[u])
        {
            if(dis[v]) continue;
            dis[v]=dis[u]+1;
            q.push(v);
        }
    }
    int ans=1e18;
    for(int i=0;i<=m;i++)
    {
        int tmp=dis[getid(n,i,1)];
        // cout<<n<<' '<<i<<' '<<tmp<<endl;
        if(tmp) ans=min(tmp,ans);
    }
    if(ans==1e18) cout<<-1<<endl;
    else cout<<ans-1<<endl;
}
signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    int t=1;
    while(t--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3608kb

input:

4 4 3 1

output:

3

result:

ok 1 number(s): "3"

Test #2:

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

input:

3 5 2 0

output:

5

result:

ok 1 number(s): "5"

Test #3:

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

input:

2 5 1 1

output:

-1

result:

ok 1 number(s): "-1"

Test #4:

score: -100
Runtime Error

input:

1 1 1 0

output:


result: