NYOJ 21コップ3個

2698 ワード

最初はBFSを使って作ったとは思わなかったのですが・・・
時間制限:1000 ms|メモリ制限:65535 KB
難易度:4
説明3つのコップが与えられ、大きさが異なり、最大のコップの水だけがいっぱいで、残りの2つは空のコップです.3つのコップの間は互いに水を注ぎ合い、コップには標識がなく、与えられたコップの体積に基づいて計算するしかない.初期状態をターゲット状態に到達させる最小回数を出力するプログラムを書く必要があります.
入力第1行の1つの整数N(0V 2>V 3 V 1<100 V 3>0)が3つのコップの体積を表す.2行目は3つの整数E 1 E 2 E 3(体積が対応するコップの体積以下)を与え、私たちが必要とする最終状態を表す.
出力各行は、対応するテストデータの最小の給水回数を出力します.目標状態出力-1に達しない場合
サンプル入力

サンプル出力

3
-1

#include <iostream>
#include <cstring>
#include <queue>
 
using namespace std;
 
int V[3],E[3]; //    、    
bool visited[102][102][102];
 
//   _         
struct cupStatus
{
    int C[3];
    int step;
};
 
//                (  )
bool isObject(cupStatus cur)
{
    int i;
    for(i=0;i<3;i++)
        if(cur.C[i]!=E[i])
            return false;
    return true;
}
 
//  
void Pour(int obj, int sour, cupStatus& cur)
{
    int differ=V[obj]-cur.C[obj];
    if(cur.C[sour]>=differ)
    {
        cur.C[obj]+=differ;
        cur.C[sour]-=differ;
    }
    else
    {
        cur.C[obj]+=cur.C[sour];
        cur.C[sour]=0;
    }
}
 
int BFS()
{
    int i,j,k;
    cupStatus init;
    queue<cupStatus> pourStatus;
 
    memset(visited,false,sizeof(visited));
 
    init.C[0]=V[0];
    init.C[1]=init.C[2]=0;
    init.step=0;
 
    pourStatus.push(init);  //       
    visited[init.C[0]][0][0]=true;  //       true
 
    while(!pourStatus.empty())
    {
        cupStatus front=pourStatus.front();
        pourStatus.pop();
 
        if(isObject(front))
            return front.step;
 
        for(i=0;i<3;i++)
        {
            for(j=1;j<3;j++)
            {
                k=(i+j)%3;
                if(front.C[i]!=0 && front.C[k]<V[k])
                {
                    cupStatus newFront=front;
                    Pour(k,i,newFront);
                    newFront.step=front.step+1;
                    if(!visited[newFront.C[0]][newFront.C[1]][newFront.C[2]])
                    {
                        visited[newFront.C[0]][newFront.C[1]][newFront.C[2]]=true;
                        pourStatus.push(newFront);
                    }
                }
            }
        }
    }
    return -1;
}
 
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        cin>>V[0]>>V[1]>>V[2];    //      
        cin>>E[0]>>E[1]>>E[2];    //        
        cout<<BFS()<<endl; 
    }
    return 0;
}

Laravelメッセージキュー

php+redis+lua分散ロックを実現