跳蚤国王和蛐蛐国王在玩一个游戏。
他们在一个n行m列的网格上排兵布阵。其中的c个格子中(0<=2c<=nm-3), 每个格子有一只跳蚤,另有c个格子,每个格子中有一只蛐蛐,剩下的nm-2c个格子 是空的。
我们定义跳蚤国王获胜,当某个时刻,网格中存在连续的k个格子,每个格子中 都是跳蚤。连续的k个格子是指,选定某个格子,选定某个方向(上,右,上左,上 右),从这个格子开始在这个方向上连续的k个格子。同理我们可以定义蛐蛐国王获 胜。
在一开始的网格上,保证不存在一方己经获胜,保证至少有3个空格子。
接下来跳蚤国王和蛐蛐国王轮流行动,跳蚤国王先手。跳蚤国王行动的时候,可 以在网格的任意一个空格子里放一只跳蚤;蛐蛐国王行动的时候,可以在网格的任意 一个空格子里放一只蛐蛐。如果某时刻某一方己经获胜,则游戏结束。
现在跳蚤国王想知道,网格中有多少个空格子,使得跳蚤国王第一步在该格子中 放一只跳蚤之后,可以在一步之内获胜。
跳蚤国王在一步之内获胜的意思是,跳蚤国王己经获胜,或者,不论蛐蛐国王下 一步如何行动,蛐蛐国王都不能获胜,且跳蚤国王在接下来的一步中都存在一种获胜 的方案。
跳蚤国王当然知道怎么做啦!但是他想考考你。