Quel est le moyen le plus efficace de remplir un rectangle d'eau ?

Question

Compte tenu d'un n par m Dans une fosse rectangulaire, quel est le plus petit nombre de seaux que l'on peut utiliser pour la remplir complètement de blocs de source d'eau ? Compte tenu de la façon dont l'eau se propage, quelle est la séquence la plus efficace pour remplir le rectangle ? Cette séquence est-elle différente si l'on essaie de remplir un carré ?

Answer 1

Un bloc d'eau devient un bloc source lorsqu'il y a au moins deux autres blocs source à côté de lui (sans compter les diagonales). Vous commencez par le bord extrême et placez deux blocs d'eau comme ceci. Cela vous donnera un carré de 2×2 de sources d'eau.

__________
|Wo      |
|oW      |
|        |
|        |
|        |

W = water source placed by you
o = water source generated by the water mechanics

Maintenant, il suffit de ramasser n'importe quel bloc source (il se remplira à nouveau), et de le déverser en diagonale du bloc le plus extérieur.

__________
|Woo     |
|oWo     |
|ooW     |
|        |
|        |

Répétez jusqu'à ce que vous atteigniez un bord. Le bloc source que vous prenez n'a pas d'importance, ils sont tous infinis (c'est-à-dire qu'ils se remplissent instantanément) à ce stade.

__________
|Woooo   |
|oWooo   |
|ooWoo   |
|oooWo   |
|ooooW   |

Comme vous pouvez le constater, pour remplir un n -un carré long, il faut n seaux (en fait, seulement 2, car après cela, vous pouvez vous resservir dans la piscine).

Pour remplir tout le rectangle, il faut déverser un seau tous les deux rangs sur un côté. Le bloc le plus au bord doit toujours être rempli.

__________
|Wooooooo|
|oWoooooo|
|ooWooooo|
|oooWoooo|
|ooooWWoW|

Donc, pour remplir un n×m vous avez besoin n + ceil((m - n) / 2) sources d'eau, avec m étant le côté le plus long. Encore une fois, seulement 2 si vous parlez de ressources, parce qu'après cela, vous puisez dans une réserve infinie.

Voici un vidéo d'un gars utilisant cette technique sur un carré :

https://www.youtube.com/watch?v=A9HVe3_1N7k?start=64

(Notez qu'il se recharge toujours à partir des blocs sources immobiles pour une raison quelconque, mais comme indiqué ci-dessus, n'importe quel bloc source fera l'affaire).

Answer 2

Cela pourrait être légèrement plus facile : Vous pouvez également remplir deux côtés adjacents avec des blocs sources :

+-------+
|WWWWWWW|
|Woooooo|
|Woooooo|
|Woooooo|
|Woooooo|
|Woooooo|
+-------+

...sans avoir à entrer dans la piscine et à marcher sur l'eau. Vous pouvez le faire en traversant seulement deux côtés. Cela peut être aussi efficace que l'excellente réponse de @lunboks :

+-------+
|1 2 3 4|
|       |
|5      |
|       |
|6      |
|7      |
+-------+

...et présente l'avantage supplémentaire que si vous placez le bloc d'angle (1) en dernier, vous pouvez regarder l'ensemble tourner en un seul mouvement fluide ! :)