1.4.5 Mother's Milk DFS深さ探索

タイトルアドレス:http://ace.delos.com/usacoprob2?S=milk3&a=noSD7NtGmGx
この問題は、実は簡単だが、最初は問題を解く考えが見つからなかった.「道に迷った」からだ.いつも純粋な数学の方法で解決しようとして、言い換えればこの問題の法則を見つけようとします.しかし、このテーマはUSACOの簡単な検索の章に置かれていたが、その後、検索の考え方で考えてみると、茅塞顿が開いた.
このような最も単純な検索問題では,検索過程における状態表現を設計し,その後状態遷移の再帰関係を確立し,最後に再帰終了条件を解析することが重要である.
例えば、この問題は、3つのバケツの総量が変わらないため、(a,b)は中間状態を表し、現在の1つ目のバケツと2つ目のバケツの牛乳量を表し、c=mc-a-bである.(ma,mb,mcはそれぞれ3つのバケツの容量を表す).そして、初期状態が(0,0)、受容状態が(0,x)であると分析する.
状態のジャンプも直感的で、毎回“現在の状態”に対して6種類の選択があって、AはBの中で傾倒して、AはCの中で傾倒して、BはAの中で傾倒して、BはCの中で傾倒して、CはAの中で傾倒して、CはBの中で傾倒します.
だからこの问题を通じて(通って)コンピュータが深く问题の特徴を探し当てることを解决することができて、私达が人為的にコンピュータのために1セットの“再帰の规则”を设置したことにほかならなくて、いつから、どのように状态が跳んで、どのように判定して终わります.それからコンピュータに“一歩一歩深く”の仕事をさせて、この仕事は私达はコンピュータに及ばないで、私达はもし“考えます”ならば、数歩も歩けないで、でたらめになります.私たちの脳はコンピュータに似ていないので、「スタック」のメカニズムがあり、前の状態を保存することができます.私たちの脳のすごいところはルールを設定することで、コンピュータの強みは「記憶」と「遍歴速度」です.

/*
ID:liuweiv2
PROG:milk3
LANG:C++
*/

#include<iostream>
#include<fstream>
using namespace std;

const int W = 21;
int ma,mb,mc;
bool isOk[W];
bool vis[W][W];


void dfs(int a,int b){
    if(vis[a][b])
        return;

    vis[a][b] = true;//            ，       。

    int c = mc - a - b;//      a,b,c

    if(a == 0)
        isOk[c] = true;

    //a->b
    if(a+b<=mb)
        dfs(0,a+b);
    else
        dfs(a-mb+b,mb);

    //a->c
    if(a+c<=mc)
        dfs(0,b);
    else
        dfs(a-mc+c,b);

    //b->a
    if(b+a<=ma)
        dfs(b+a,0);
    else
        dfs(ma,b-ma+a);

    //b->c
    if(b+c<=mc)
        dfs(a,0);
    else
        dfs(a,b-mc+c);

    //c->a
    if(c+a<=ma)
        dfs(c+a,b);
    else
        dfs(ma,b);

    //c->b
    if(c+b<=mb)
        dfs(a,c+b);
    else
        dfs(a,mb);

}


int main(){
    ifstream infile;
    ofstream outfile;
    infile.open("milk3.in");
    outfile.open("milk3.out");

    infile>>ma>>mb>>mc;

    //memset(isOk,0,sizeof(isOk));
    //memset(vis,0,sizeof(vis));
    for(int i=0;i<W;i++)
    {
        isOk[i] = false;
        for(int j=0;j<W;j++)
            vis[i][j] = false;
    }


    dfs(0,0);


    bool first = true;
    for(int i=0;i<=mc;i++)
        if(isOk[i]){
            if(first){
                outfile<<i;
                first = false;
            }
            else
                outfile<<" "<<i;
        }
    outfile<<endl;

    return 0;
}