P4701 粘骨牌

题目描述

一个 $n \times m$ 的棋盘,除了某一个位置,其它所有位置都被 $1 \times 2$ 的多米诺骨牌覆盖,所以一共有 $\frac{nm - 1}{2}$ 个多米诺骨牌。 Alice 可以进行任意多次移动,每次移动需要保证移动后多米诺骨牌不超出棋盘,且不能存在两个多米诺骨牌重叠。 棋盘上有若干个特殊位置,一旦它们露出来,你就输了,所以你要避免 Alice 的移动使这些位置露出来。 你可以选择固定任意多个多米诺骨牌,固定一个骨牌需要一定的代价,身为 Bob 的你希望用最少的代价,使得无论 Alice 怎么移动,那些特殊位置都不会露出来,求出这个最小代价。 如果无论怎么固定,都不能满足,输出 "GG"。

输入格式

输出格式