问题 3603 --玩诈欺的小杉

3603: 玩诈欺的小杉

题目描述

  小杉的幻想来到了经典日剧《诈欺游戏》的场景里……
他正在参加诈欺游戏的第四回合(-.-干嘛幻想这么郁闷的场景……)。

话说第四回合不就是“人生”吗……
总之,无论如何,小杉身为新一代的松田翔太,必须要赢得这场游戏!
第四回合的参赛者只有一个人(其他人不都选择退赛了吗……)
庄家贝洛尼亚告诉了小杉第四回合的游戏。

(若对情节有任何疑问,请观看原剧)
是这样的,在小杉的面前有一个N行M列的棋盘,棋盘上有N*M个有黑白棋的棋子(一面为黑,一面为白),一开始都是白面朝上。

小杉可以对任意一个格子进行至多一次的操作(最多进行N*M个操作),该操作使得与该格同列的上下各2个格子以及与该格同列的左右各1个格子以及该格子本身翻面。

例如,对于一个5*5的棋盘,仅对第三行第三列的格子进行该操作,得到如下棋盘(0表示白面向上,1表示黑面向上)。
00100
00100
01110
00100
00100
对一个棋盘进行适当的操作,使得初始棋盘(都是白面朝上)变成已给出的目标棋盘的操作集合称作一个解法。

小杉的任务是对给出的目标棋盘求出所有解法的总数。

输入

每组测试数据的
第一行有3个正整数,分别是N和M和T(1<=N,M<=20,1<=T<=5)
接下来T个目标棋盘,每个目标棋盘N行,每行M个整数之前没有空格且非0即1,表示目标棋盘(0表示白面朝上,1表示黑面朝上)
两个目标棋盘之间有一个空行。

特别地,对于30%的数据,有1<=N,M<=15

输出

对每组数据输出T行,每行一个整数,表示能使初始棋盘达到目标棋盘的解法总数

样例输入输出

输入#1 复制
4 4 2
0010
0010
0111
0010

0010
0110
0111
0010

输出#1 复制
1
1

提示

对于输入的数据,两个目标棋盘各有一种解法
1:
0000
0000
0010
0000
2:
1011
1101
0111
1011
其中1表示对该格进行操作,0表示不操作

序号 标题 作者 发表时间 费用 订购数 操作