1267: 非常可乐

http://tjuacm.chaosheng.top/problem.php?id=1267
参考 https://blog.csdn.net/tigerisland45/article/details/52207660

用到的是BFS+模拟
对于很多求最快，最短，最少的问题，都可以用bfs来做
之前几题求的是所有情况，所以用的是dfs。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 110;

int s, n, m, avg;
bool vis[N][N][N];

struct node{
    int s, n, m;
    int step;
};

int bfs(){
    queue<node> q;
    node f;
    f.s = s;
    f.n = 0;
    f.m = 0;
    f.step = 0;
    q.push(f);
    vis[f.s][f.n][f.m] = true;

    while(!q.empty()){
        f = q.front();
        q.pop();

        //满足条件
        if((f.s == f.n && f.n == avg) || (f.s == f.m && f.m == avg) || (f.n == f.m && f.n == avg)){
            return f.step;
        }

        node v; //新的状态 

        //s->n
        if(f.s && f.n < n){
            if(f.s > n - f.n) {   //f.s大于 n剩余容量 
                v.s = f.s - (n - f.n);
                v.n = n;
                v.m = f.m;
            }else{
                v.s = 0;
                v.n = f.n + f.s;
                v.m = f.m;
            }
            if(!vis[v.s][v.n][v.m])    {
                vis[v.s][v.n][v.m] = true;
                v.step = f.step + 1;
                q.push(v);
            }
        }

        //s->m
        if(f.s && f.m < m){
            if(f.s > m - f.m) {   //f.s大于 m剩余容量 
                v.s = f.s - (m - f.m);
                v.n = f.n;
                v.m = m;
            }else{
                v.s = 0;
                v.n = f.n;
                v.m = f.m + f.s;
            }
            if(!vis[v.s][v.n][v.m])    {
                vis[v.s][v.n][v.m] = true;
                v.step = f.step + 1;
                q.push(v);
            }
        }

        //n->s
        if(f.n && f.s < s){
            if(f.n > s - f.s) {   //f.n大于 s剩余容量 
                v.s = s;
                v.n = f.n - (s - f.s);
                v.m = f.m;
            }else{
                v.s = f.s + f.n;
                v.n = 0;
                v.m = f.m;
            }
            if(!vis[v.s][v.n][v.m])    {
                vis[v.s][v.n][v.m] = true;
                v.step = f.step + 1;
                q.push(v);
            }
        }

        //n->m
        if(f.n && f.m < m){
            if(f.n > m - f.m) {   //f.n大于 m剩余容量 
                v.s = f.s;
                v.n = f.n - (m - f.m);
                v.m = m;
            }else{
                v.s = f.s;
                v.n = 0;
                v.m = f.m + f.n;
            }
            if(!vis[v.s][v.n][v.m])    {
                vis[v.s][v.n][v.m] = true;
                v.step = f.step + 1;
                q.push(v);
            }
        }

        //m->s
        if(f.m && f.s < s){
            if(f.m > s - f.s) {   //f.n大于 s剩余容量 
                v.s = s;
                v.n = f.n;
                v.m = f.m - (s - f.s);
            }else{
                v.s = f.s + f.m;
                v.n = f.n;
                v.m = 0;
            }
            if(!vis[v.s][v.n][v.m])    {
                vis[v.s][v.n][v.m] = true;
                v.step = f.step + 1;
                q.push(v);
            }
        }

        //m->n
        if(f.m && f.n < n){
            if(f.m > n - f.n) {   //f.n大于 m剩余容量 
                v.s = f.s;
                v.n = n;
                v.m = f.m - (n - f.n);
            }else{
                v.s = f.s;
                v.n = f.n + f.m;
                v.m = 0;
            }
            if(!vis[v.s][v.n][v.m])    {
                vis[v.s][v.n][v.m] = true;
                v.step = f.step + 1;
                q.push(v);
            }
        }
    }
    return -1;
}

int main(){
    while(cin >> s >> n >> m){
        if(s == 0 && n == 0 && m == 0) break;
        if(s % 2 == 1) {
            printf("NO\n");
            continue;
        }
        avg = s / 2;
        memset(vis, false, sizeof(vis));
        int ans = bfs();
        if(ans == -1) printf("NO\n");
        else printf("%d\n", ans);    
    }
    return 0;
}