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.

题目描述

编题好累，直接说题意了： 在一个n*m的矩阵中，现在有若干个中国象棋棋子，现在需要新加一枚棋子到空白处， 求有多少种方案使得新加的棋子不被已有的棋子攻击？ 象棋棋子移动规则：（同中国象棋） 帅(或者将) 可一次向上下左右移动一个单位 车 可沿水平或者垂直方向一次移动多个单位,中间不能有棋子隔开 马 可走"日"字，但是不能在"日"字长边与马相邻出有棋子 炮 可沿水平或者垂直方向越过最近一个棋子移动到次近的棋子处 象 可走"田"字，但是"田"字中央不能有棋子存在 士 可向斜线放下一次移动一个单位 兵 可一次向上下左右移动一个单位

输入格式

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

输出格式

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

3 3
000
010
000

4

附件

file

提示

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

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

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