Inc CUBE Walking

この問題はUnion Findなどを用いて$O(HW)$で解くことができます。

立方体がどこにあるのか、インクのついた面がどこを向いているのか (前後左右上下)、というような情報持った状態を$6HW$個用意します。
(例) $(1,1,下), (2,4,前), (5,3,左)$など

そして、遷移可能な状態を連結させます。
例えば、$(1,1)$にあってインクのついた面が右にある立方体が$(1,2)$に移動すると、インクのついた面は下を向きます。
このとき、$(1,1,右)$と$(1,2,下)$の状態を連結させればよいです。

立方体が多くの面を赤く塗ることができるというのは、遷移できる状態の中で、
インクのついた面が「下」であるものが多いことと同値です。
よって答えは、連結成分の中で$(i,j,下)$であるものの個数の最大値です。