问题 4341 --PS毕业照

4341: PS毕业照★★

时间限制: 1 Sec  内存限制: 512 MB
提交: 105  解决: 45
[提交][状态][命题人:]

题目描述

你拍了毕业生的毕业照。 图片可以看作是一个n×n的矩阵A,A中的每个元素为0或1,分别代表空白背景或学生。
不过老师们忙得没时间和学生合影,只自己拍了一张合影。 这张照片可以看作是一个 1×m 的矩阵 B,其中每个元素是 2,代表一位老师。
作为Photoshop的高手,您的工作是将照片B放入照片A,并具有以下约束:
1. 不允许分割、旋转或缩放图片,只能平移。
2. 矩阵 B 中的每个元素都应该与 A 中的元素完全重叠,并且每个老师都应该与空白背景重叠,而不是遮挡学生。
请计算将照片 B 放入照片 A 的可能方式。

输入

第一行包含两个整数 n,m(1≤n,m≤2000),表示照片 A 和 B 的大小。
在接下来的n行中,每行包含n个字符'0'或'1',代表矩阵A。
最后一行包含m个字符'2',代表矩阵B。

输出

输出一行,包含一个整数,表示方案数。
样例输入
Copy
5 3
00000
01110
01110
01110
00000
222
样例输出
Copy
6

提示

来源

[提交][状态]