この問題はUnion Findなどを用いてで解くことができます。
立方体がどこにあるのか、インクのついた面がどこを向いているのか (前後左右上下)、というような情報持った状態を個用意します。
(例) など
そして、遷移可能な状態を連結させます。
例えば、にあってインクのついた面が右にある立方体がに移動すると、インクのついた面は下を向きます。
このとき、との状態を連結させればよいです。
立方体が多くの面を赤く塗ることができるというのは、遷移できる状態の中で、
インクのついた面が「下」であるものが多いことと同値です。
よって答えは、連結成分の中でであるものの個数の最大値です。