I was working on the Silver Milk Pails question and I was able to solve it by floodfilling each state of milk buckets. However, I was unsure of what the time complexity would be for this problem. At max how many states are visited using floodfill? Because I could not properly analyze time complexity for the floodfill solution, it was not conceivable at first that floodfill itself could be a solution. Does anyone have an analysis to the time complexity for this particular problem?
My code:
void ff(int a, int b, int k){
if(visited[a][b][k]||k>K){ return; }
ans = min(ans, (int)abs(b+a-M));
visited[a][b][k]=true;
total++;
ff(X,b,k+1);
ff(a,Y,k+1);
ff(0,b,k+1);
ff(a,0,k+1);
int poured1=min(X-a,b);
int poured2=min(Y-b,a);
ff(a+poured1,b-poured1,k+1);
ff(a-poured2,b+poured2,k+1);
}
int main() {
IO("pails");
cin >> X >> Y >> K >> M;
ff(0,0,0);
cout << ans << nl;
}