HDU 1495 비상 콜라 (물 붓 기 문제 bfs + 시 뮬 레이 션)

HDU 1495 비상 콜라 (물 붓 기 문제 bfs + 시 뮬 레이 션)
운동 후에 콜 라 를 마 시 는 것 은 즐 거 운 일이 라 고 생각 하 시 겠 지만 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
문제 풀이 방향:
1. 경로 가 가장 짧 고 시간 이 가장 짧 으 며 조작 이 가장 적 고 횟수 가 가장 적 으 며 가장 빠 른 것 은 보통 널리 검색 합 니 다. 2. 전형 적 인 물 붓 기 문제: 물 붓 는 과정, 6 가지, 물병 A, 컵 B, 컵 C, A - > B A - > C, B - > A, C - > A, B - > C 를 모 의 합 니 다.C - > B 3. 물 을 붓 는 과정 에서 한 컵 의 수량 이 줄 어 들 면 반드시 해당 컵 의 수량 이 증가 해 야 한다.

#include
#include
#include
#include
#include
#include
#define INF 0x7fffffff
using namespace std;
typedef struct node {
    int z;//         
    int x;//          
    int y;//          
    int step;
} Node;
Node temp,t;
queueq;
int book[105][105][105];//    
int main() {
    int s,n,m;
    while(cin>>s>>n>>m) {
        if(s==0&&n==0&&m==0) {
            break;
        }
        int flag=0;
        if(s%2!=0) {//    ，            ，      
            flag=0;
        }
        else {
            int tol=s/2;//    
            memset(book,0,sizeof(book));
            temp.x=0;//    
            temp.y=0;
            temp.z=s;
            book[s][0][0]=1;//  
            temp.step=0;
            q.push(temp);
            while(!q.empty()) {
                temp=q.front();
                q.pop();
                //        ,         
                if(((temp.x==temp.y)&&temp.z==0)||((temp.x==temp.z)&&temp.y==0)||((temp.y==temp.z)&&temp.x==0)) {
                    cout<.step<;
                    flag=1;
                    break;
                }
                //A->B   （  B    ，   A     ）
                if(temp.x.z>0) {
                    //    ，    A      B    B  
                    //    ，A       B   ，        
                    t.x=min(n,temp.z+temp.x);
                    t.y=temp.y;
                    t.z=temp.z-(t.x-temp.x);
                    t.step=temp.step+1;
                    //  book        
                    if(book[t.z][t.x][t.y]==0){
                        book[t.z][t.x][t.y]=1;
                        q.push(t);
                    }
                }
                if(temp.y.z>0) {//A->C
                    t.y=min(m,temp.z+temp.y);
                    t.x=temp.x;
                    t.z=temp.z-(t.y-temp.y);
                    t.step=temp.step+1;
                    if(book[t.z][t.x][t.y]==0){
                        book[t.z][t.x][t.y]=1;
                        q.push(t);
                    }
                }
                if(temp.z.x>0) {//B->A
                    t.z=temp.z+temp.x;
                    t.y=temp.y;
                    t.x=0;
                    t.step=temp.step+1;
                    if(book[t.z][t.x][t.y]==0){
                        book[t.z][t.x][t.y]=1;
                        q.push(t);
                    }
                }
                if(temp.z.y>0) {//C->A
                    t.z=temp.z+temp.y;
                    t.y=0;
                    t.x=temp.x;
                    t.step=temp.step+1;
                    if(book[t.z][t.x][t.y]==0){
                        book[t.z][t.x][t.y]=1;
                        q.push(t);
                    }
                }
                if(temp.x>0&&temp.yC
                    t.y=min(m,temp.y+temp.x);
                    t.z=temp.z;
                    t.x=temp.x-(t.y-temp.y);
                    t.step=temp.step+1;
                    if(book[t.z][t.x][t.y]==0){
                        book[t.z][t.x][t.y]=1;
                        q.push(t);
                    }
                }
                if(temp.y>0&&temp.xB
                    t.x=min(n,temp.y+temp.x);
                    t.z=temp.z;
                    t.y=temp.y-(t.x-temp.x);
                    t.step=temp.step+1;
                    if(book[t.z][t.x][t.y]==0){
                        book[t.z][t.x][t.y]=1;
                        q.push(t);
                    }
                }
            }
            while(!q.empty()) {
                q.pop();
            }
        }
        if(flag==0){
            cout<<"NO"<;
        }
    }
    return 0;
}