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

题解

题目大致给你一个由0和1构成的 $n*n$ 的矩阵，然后给你一个 $1*m$ 的矩阵，问$1*m$ 的矩阵在只平移的情况下且不覆盖1的情况下，放在 $n*n$ 的矩阵中有多少种放法。

这是一道模拟暴力题，只需要对于 $n*n$ 的矩阵每一行都分别判断 $(n-m)$ 次即可。

稍微注意一下判断的方法，比如用一个变量记录有多少个1在 $1*m$ 的矩阵中，随着平移增加减少，不要超了时间就好。

代码

代码如下：

#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;
}