题解 P3139 【[USACO16FEB]牛奶桶Milk Pails】

2018-05-02 19:58:40


一看到此题就联想到了以前用广搜做的一道类似的题......

广搜做很简单,我还提心吊胆的加了优化,防止TLE

附上评测结果 用时: 0ms / 内存: 3246KB的代码:

#include <bits/stdc++.h>
using namespace std;
int b1,b2,need,ans = INT_MAX,kk;
struct Node{int x,y,cnt;};
//x为1桶的单位数,y为2桶的单位数
void bfs()
{
    bool vis[101][101][101] = {};memset(vis,0,sizeof(vis));//状态记录数组
    queue<Node> q;//防止MLE
    q.push({0,0,0});vis[0][0][0] = 1;
    while (!q.empty())
    {
        Node n = q.front();q.pop();
        if(n.cnt == kk || n.x == 0 || n.y == 0)//判断 如两个桶里有任意一个为0,也做一次检查(之后可以一直倒空这个桶)
        {
            ans = min(ans,abs(n.x + n.y - need));//cout << n.x + n.y << endl;
            if (n.cnt == kk) continue;//防止不必要状态扩展
        }
        int x = n.x,y = n.y,cnt = n.cnt + 1;//扩展
        if(!vis[b1][y][cnt]) q.push({b1,y,cnt});
        vis[b1][y][cnt] = 1;
        if(!vis[x][b2][cnt]) q.push({x,b2,cnt});
        vis[x][b2][cnt] = 1;
        if(!vis[0][y][cnt]) q.push({0,y,cnt});
        vis[0][y][cnt] = 1;
        if(!vis[x][0][cnt]) q.push({x,0,cnt});
        vis[x][0][cnt] = 1;
        int Y = x + y,X = 0;
        if(Y > b2) X = Y - b2,Y = b2;
        if(!vis[X][Y][cnt]) q.push({X,Y,cnt});
        vis[X][Y][cnt] = 1;
        X = x + y,Y = 0;
        if(X > b1) Y = X - b1,X = b1;
        if(!vis[X][Y][cnt]) q.push({X,Y,cnt});
        vis[X][Y][cnt] = 1;
    }
    printf("%d",ans);
}
int main ()
{
    scanf("%d%d%d%d",&b1,&b2,&kk,&need);
    bfs();
    return 0;
}