항 전 1495 비상 콜라

콜라
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 8576    Accepted Submission(s): 3397
Problem Description
운동 후에 콜 라 를 마 시 는 것 은 즐 거 운 일이 라 고 생각 하 시 겠 지만 seeyou 는 그렇게 생각 하지 않 습 니 다.매번 seeyou 가 콜 라 를 산 후에 소 는 seeyou 와 함께 이 콜 라 를 공유 하 라 고 요구 하고 꼭 마셔 야 하 는 것 이 seeyou 만큼 많 기 때문이다.그러나 seeyou 의 손 에는 두 개의 컵 만 있 는데 그들의 용량 은 각각 N 밀리리터 와 M 밀리리터 콜라 의 부 피 는 S (S < 101) 밀리리터 (한 병 을 채 울 수 있 음) 이 고 그들 세 개 사이 에 콜 라 를 서로 부 을 수 있다 (모두 눈금 이 없 으 며 S = = N + M, 101 ＞ S ＞ 0, N ＞ 0, M ＞ 0).똑똑 한 ACMER. 똑 같이 나 눌 수 있다 고요?콜 라 를 따 르 는 최소한 의 횟수 를 출력 할 수 있다 면 'NO' 를 출력 할 수 없다 면.
 
Input
세 개의 정수: S 콜라 의 부피, N 과 M 은 두 컵 의 용량 으로 '000' 으로 끝난다.
 
Output
동점 이 된다 면 최소한 거꾸로 해 야 할 횟수 를 출력 하 십시오. 그렇지 않 으 면 "NO" 를 출력 하 십시오.
 
Sample Input

   
   
   
   

    
    
    
    7 4 3
4 1 3
0 0 0
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    NO
3
   
   
   
   

 
Author
seeyou
 
초지 에 쏟 아 지 는 과정 을 모 의 한 것 입 니 다. 우 리 는 컵 에 모두 번 호 를 매 깁 니 다. 1, 2, 1, 3, 2, 1, 2, 3, 3, 1, 3, 2.자신 이 자신 에 게 줄 수 없 기 때문에 모두 6 개의 조작 이 있 습 니 다. 조작 중 에 두 가지 가능성 이 있 습 니 다. 하 나 는 가득 채 울 수 있 고 나머지 가 있 습 니 다.다른 하 나 는 남 은 것 이 없다 는 것 이다.
이 동작 은 다음 과 같 습 니 다.

        for(int i=0;i<3;i++)
        {
            for(int j=0;j<3;j++)
            {
                if(i==j)continue;//    
                if(now.num[i]<=rq[j]-now.num[j])//      ，  rq        ，num              。
                {
                    nex.num[j]=now.num[j]+now.num[i];
                    nex.num[i]=0;
                }
                else//         
                {
                    nex.num[i]=now.num[i]-(rq[j]-now.num[j]);
                    nex.num[j]=rq[j];
                }
                for(int ii=0;ii<3;ii++)//    
                {
                    if(ii==i||ii==j)
                    continue;
                    nex.num[ii]=now.num[ii];
                }
                nex.output=now.output+1;
                if(vis[nex.num[0]][nex.num[1]][nex.num[2]]==0)//  vis  
                {
                    vis[nex.num[0]][nex.num[1]][nex.num[2]]=1;
                    s.push(nex);
                }
            }
        }

그리고 목 표를 달성 할 수 있 는 지 를 판단 하 는 것 이다.

        if(now.num[0]==now.num[1]&&now.num[2]==0)
        {
            printf("%d
",now.output);
            return ;
        }
        if(now.num[0]==now.num[2]&&now.num[1]==0)
        {
            printf("%d
",now.output);
            return ;
        }
        if(now.num[1]==now.num[2]&&now.num[0]==0)
        {
            printf("%d
",now.output);
            return ;
        }

그 다음 에 완전한 AC 코드 입 니 다.

#include<stdio.h>
#include<queue>
#include<string.h>
using namespace std;
struct qingkuang
{
    int num[3];
    int output;
}now,nex;
int vis[102][102][102];
int rq[3];
void bfs(int ss,int n,int m)
{
    memset(vis,0,sizeof(vis));
    queue<qingkuang>s;
    now.num[0]=ss;
    now.num[1]=n;
    now.num[2]=m;
    vis[ss][n][m]=1;
    now.output=0;
    s.push(now);
    while(!s.empty())
    {
        now=s.front();
        if(now.num[0]==now.num[1]&&now.num[2]==0)
        {
            printf("%d
",now.output);
            return ;
        }
        if(now.num[0]==now.num[2]&&now.num[1]==0)
        {
            printf("%d
",now.output);
            return ;
        }
        if(now.num[1]==now.num[2]&&now.num[0]==0)
        {
            printf("%d
",now.output);
            return ;
        }
        s.pop();
        for(int i=0;i<3;i++)
        {
            for(int j=0;j<3;j++)
            {
                if(i==j)continue;
                if(now.num[i]<=rq[j]-now.num[j])
                {
                    nex.num[j]=now.num[j]+now.num[i];
                    nex.num[i]=0;
                }
                else
                {
                    nex.num[i]=now.num[i]-(rq[j]-now.num[j]);
                    nex.num[j]=rq[j];
                }
                for(int ii=0;ii<3;ii++)
                {
                    if(ii==i||ii==j)
                    continue;
                    nex.num[ii]=now.num[ii];
                }
                nex.output=now.output+1;
                if(vis[nex.num[0]][nex.num[1]][nex.num[2]]==0)
                {
                    vis[nex.num[0]][nex.num[1]][nex.num[2]]=1;
                    s.push(nex);
                }
            }
        }
    }
    printf("NO
");
    return ;
}
int main()
{
    int s,n,m;
    while(~scanf("%d%d%d",&s,&n,&m))
    {
        if(s==0&&n==0&&m==0)break;
        rq[0]=s;
        rq[1]=n;
        rq[2]=m;
        bfs(s,0,0);
    }
}