You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

蒙自一中的同学在课间有丰富多彩的活动，其中一部分同学很喜欢下象棋。

同时，邓老师说这次比赛不能有太多满分，所以让出题组出一道毒瘤题卡你们，所以根据象棋规则改编了一下，再加上实力强大的 kcs007 王老师，就有了如下这道题。

题目描述

在一个 $n\times m$ 的矩阵中，现在有若干个中国象棋棋子。

现在需要新加一枚棋子到空白处，求有多少种方案使得新加的棋子不被已有的棋子攻击？ （也就是问有多少个空白格子不会被任何棋子攻击）

中国象棋棋子攻击范围详解

1. 帅（将） 代表数字1

• 攻击范围：上下左右 1步
• 示例：
  • 帅在 (2,2) 可攻击：
    • (1,2)
    • (3,2)
    • (2,1)
    • (2,3)

2. 车（車） 代表数字2

• 攻击范围：
  • 直线无限延伸（上下左右）
  • 会被其他棋子阻挡
• 示例：
  • 车在 (3,3) 可攻击：
    • 整行 (3,1) 到 (3,m)
    • 整列 (1,3) 到 (n,3)
    • 从自己的位置开始延申，直到遇到第一个棋子后停止。

3. 马（馬） 代表数字3

• 攻击范围：
  • 走"日"字（2×1或1×2）
  • 蹩马腿规则：
  • 当马的某个方向（上下左右其中一个）的相邻格子有其他棋子遮挡，那么这个方向的两个“日”字无法走到。
  • 见下图。

4. 炮（砲） 代表数字4

• 攻击范围：
  • 攻击需跳过一个棋子
• 示例：
  • 炮在 (3,3)：
    • 可攻击 (3,5) 若 (3,4) 有子
    • 不能攻击 (3,5) 若 (3,4) 无子

5. 象（相） 代表数字5

• 攻击范围：
  • 走"田"字（对角2步）
  • 卡象眼：田字中心有子则不能走
• 示例：
  • 象在 (2,2)：
    • 可攻击 (4,4) 若 (3,3) 无子
    • 不能攻击 (4,4) 若 (3,3) 有子

6. 士（仕） 代表数字6

• 攻击范围：
  • 斜线走1步
• 示例：
  • 士在 (2,2) 可攻击：
    • (1,1)
    • (1,3)
    • (3,1)
    • (3,3)

7. 兵（卒） 代表数字7

• 攻击范围：上下左右 1步
• 示例：
  • 兵在 (2,2) 可攻击：
    • (1,2)
    • (2,1)
    • (2,3)
    • (3,2)

走子规则图解

帅：（红色代表攻击范围，不受其他棋子影响）举例棋盘大小 $5\times 5$。

兵：（红色代表攻击范围，不受其他棋子影响）举例棋盘大小 $5\times 5$。

马：（红色代表攻击范围，黄色代表可能影响攻击范围的其他棋子）举例棋盘大小 $5\times 5$。

炮：（红色代表攻击范围，黄色代表可能影响攻击范围的其他棋子） 举例棋盘大小 $6\times 6$。

车：（红色代表攻击范围，黄色代表可能影响攻击范围的其他棋子）举例棋盘大小 $5\times 5$。

象：（红色代表攻击范围，黄色代表可能影响攻击范围的其他棋子）举例棋盘大小 $5\times 5$。

士：（红色代表攻击范围，不受其他棋子影响）举例棋盘大小 $5\times 5$。

输入格式

测试数据先输入两个整数 $n,m$，代表矩阵的长和宽。 接下来 $n$ 行，每行 $m$ 个数字，代表初始棋盘状态： 0表示空白，1表示帅，2表示车，3表示马，4表示炮，5表示象，6表示士，7表示兵。

输出格式

对于每组测试数据，输出答案。

3 3
000
010
000

4

样例解释

$(1,1),(1,3),(3,1),(3,3)$ 不会被攻击到。

附件

大样例

提示

对于20%的数据，棋盘上没有任何棋子

对于50%的数据，棋盘上没有炮和车

对于100%的数据，$1\le n,m\le1000$