HDU 1495 아주 콜라 dfs 컵 두 개 상태

콜라
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 13223 Accepted Submission(s): 5308
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 은 두 컵 의 용량 으로 '0 0' 으로 끝난다.
출력 을 똑 같이 나 눌 수 있다 면 최소 거꾸로 해 야 할 횟수 를 출력 하 십시오. 그렇지 않 으 면 출력 "NO" 입 니 다.
Sample Input 7 4 3 4 1 3 0 0 0
Sample Output NO 3
제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=1495
제목

         ，       ，       ，              ？             ，     'NO'。

해제

  ，      ，       ，         ，         。
           bfs  ，            ，              ，           101，           101x101 。
             ，  cup[2]      ，         。 cup[0]       cup[1]     。
      ：
（1）            ，        ，      i     j，      i   0，  j    。
（2）amount = min(cup[j], u.v[i]+u.v[j]) - u.v[j];               。
（3）      ：cup[0] == cup[2] && cup[1] == 0

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define INF 0xffffffff
using namespace std;

const int maxn = 105;

int vis[maxn][maxn];
int cup[3];

struct Node{
    int v[3];
    int t;
};

void solve(){
    queue q;
    Node st;
    st.v[0] = st.v[1] = 0, st.v[2] = cup[2];
    st.t = 0;
    q.push(st);
    vis[st.v[0]][st.v[1]] = 1;
    while(!q.empty()){
        Node u = q.front();
        q.pop();
        if(u.v[0] == u.v[2] && u.v[1] == 0){
            printf("%d
", u.t);
            return;
        }
        //         
        for(int i=0; i<3; i++){
            for(int j=0; j<3; j++){
                if(i != j){
                    if(u.v[i] == 0 || u.v[j] == cup[2]) continue;
                    int amount = min(cup[j], u.v[i]+u.v[j]) - u.v[j];
                    Node u1;
                    memcpy(&u1, &u, sizeof(u));
                    u1.v[i] -= amount;
                    u1.v[j] += amount;
                    if(!vis[u1.v[0]][u1.v[1]]){
                        vis[u1.v[0]][u1.v[1]] = 1;
                        u1.t = u.t + 1;
                        q.push(u1);
                    }
                }
            }
        }
    }
    printf("NO
");
}

int main(){
    int a, b, c;
    while(scanf("%d%d%d", &c, &a, &b) == 3 && (a||b||c)){
        if(a0] = a, cup[1] = b, cup[2] = c;
        memset(vis, 0, sizeof(vis));
        solve();
    }
    return 0;
}