UVA 10603 Fill(正確代碼雖然很搓，網上許多代碼都不能AC)

題目鏈接：click here~

此題我估計是加強過數據，在我糾結了很久的時候我交了好幾份網上的代碼不是WA就是TLE。在我很迷茫的時候我又交了一份，AC了(雖然我用隨機數據找到了他代碼一個不能過的數據)。

給了我信心，然後我拿他的代碼用隨機數跟我的代碼進行測試，再用FC找不同。。發現了一個致命的錯誤，一般來說，BFS或者DFS都是需要有一個vis數組或者哈希來判重，但是此題判重是有很大問題的，同樣對於3個水杯的狀態，在3步下也許流量是50，然後這個狀態被標記，5步的時候又出現了這個狀態（可以理解為另一個分支），但是流量卻是35，如果用個二維數組判重（沒有必要用三維的，因為和是一樣的，二維就可以了），那麼這個狀態的流量就不會更新，題目的意思卻是說要用最小的流量去到達這個狀態，不管是得到最終的目標還是比目標小最近目標的狀態。

所以我感覺這題的標准解法應該不是 bfs，因為可以說是算暴力了，每一次的狀態（如果流量比上一個到這個狀態的流量少）都需要更新，不斷更新直到最後。在uva toolkit上此題的思路是dp或dijkstra。這2樣還沒怎麼搞不太會，建圖也想不到想法，感覺就算建了還是搜索的東西啊

雖然A了，但是感覺不爽啊。另外我找的那個A了的代碼沒過的數據是：33 12 113 6

他的結論是 174 6，我的結論是171 6，在uva toolkit上也是我的答案，但是我覺得他的思路應該是正確的，沒細看。。實在是太長了。

如果有想法的歡迎留言。

代碼供參考：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
#define NMAX 20000
typedef int state[3];
state st[NMAX],a;
int pour[NMAX];
int record[205];
int target;
int vis[205][205],vispour[205][205];
int try_to_insert(int x,int tpour)
{
    state &k = st[x];
    if(vis[k[0]][k[1]] != 1 || vispour[k[0]][k[1]] > tpour)
    {
        vis[k[0]][k[1]] = 1;
        vispour[k[0]][k[1]] = tpour;
        return 1;
    }
    return 0;
}
int main()
{
//    freopen("input.txt","r",stdin);
//    freopen("o.txt","w",stdout);
    int i,j,t,ans;
    scanf("%d",&t);
    while(t--)
    {
        memset(record,0,sizeof(record));
        memset(vis,0,sizeof(vis));
        memset(vispour,0,sizeof(vis));
        scanf("%d%d%d%d",&a[0],&a[1],&a[2],&target);
        st[1][0] = st[1][1] = 0;
        st[1][2] = a[2];
        memset(pour,0,sizeof(pour));
        record[a[2]] = 1;
        int front = 1,rear = 2;
        vis[0][0] = 1;
        bool flag = false;
        while(front < rear)
        {
            for(i = 0; i < 3; i++)
                if(record[st[front][i]] == 0 || pour[record[st[front][i]]] > pour[front])
                    record[st[front][i]] = front;
            for(i = 0; i < 3; i++)
                if(st[front][i] == target)
                {
                    if(flag)
                        ans = pour[ans] > pour[front]?front:ans;
                    else
                            ans = front;
                    flag = true;
                    break;
                }
            for(i = 0; i < 3; i++)
            {
                state &w = st[front];
                if(w[i] != 0)
                {
                    for(j = 0; j < 3; j++)
                    {
                        if(i == j || (i != j && w[j] == a[j])) continue;
                        state &temp = st[rear];
                        memcpy(temp,w,sizeof(w));
                        int pp;
                        if(w[i] + w[j] > a[j])
                        {
                            pp = a[j] - w[j];
                            temp[i] = w[i] - pp;
                            temp[j] = a[j];
                        }
                        else
                        {
                            pp = w[i];
                            temp[i] = 0;
                            temp[j] = w[j] + pp;
                        }
                        int tpour;
                            tpour = pour[front] + pp;
                        if(try_to_insert(rear,tpour))
                        {
                            pour[rear] = tpour;
                            rear++;
                        }
                    }
                }
            }
            front++;
        }
        if(record[target] == 0)
        {
            for(i = target; record[i] == 0; i--);
            printf("%d %d\n",pour[record[i]],i);
        }
        else printf("%d %d\n",pour[ans],target);
    }
    return 0;
}