# 2021牛客暑期多校训练营1 D题 Determine the Photo Position

## 题目描述

You have taken the graduation picture of graduates. The picture could be regarded as a matrix A of $n×n$ , each element in A is 0 or 1, representing a blank background or a student, respectively.

However, teachers are too busy to take photos with students and only took a group photo themselves. The photo could be regarded as a matrix B of $1×m$ where each element is 2 representing a teacher.

As a master of photoshop, your job is to put photo B into photo A with the following constraints:

• you are not allowed to split, rotate or scale the picture, but only translation.
• each element in matrix B should overlap with an element in A completely, and each teacher should overlap with a blank background, not shelter from a student.

Please calculate the possible ways that you can put photo B into photo A.

## 输入描述:

The first line contains two integers $n,m(1≤n,m≤2000)$ indicating the size of photos A and B.

In the next $n$ lines,each line contains $n$ characters of '0' or '1',representing the matrix A.

The last line contains $m$ characters of '2', representing matrix B.

## 输出描述:

Output one integer in a line, indicating the answer.

## 示例1

### 输入

5 3
00000
01110
01110
01110
00000
222

### 输出

6

## 示例2

### 输入

3 2
101
010
101
22

### 输出

0

## 示例3

### 输入

3 1
101
010
101
2

### 输出

4

## 代码

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
using namespace std;
const int maxn = 2e3 + 10;

int n, m;
char s[maxn][maxn];
string str;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> s[i][j];
}
}
cin >> str;
int ans = 0;
for (int i = 1; i <= n; i++) {
int num = 0;
for (int j = 1; j <= m; j++) {
if (s[i][j] == '1')
num++;
}
if (num == 0) ans++;
for (int j = m + 1; j <= n; j++) {
if (s[i][j] == '1') num++;
if (s[i][j - m] == '1') num--;
if (num == 0) ans++;
}
}
cout << ans;
return 0;
}