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