2023 深信服笔试 0920

笔试时间：2023年9月20日秋招

备注：第三题暂无题解

第一题

题目：馍馍检测病毒

馍馍发现了一种新型网络病毒，可以隐藏在图片中，图片可以简单的看成一个N X N的矩阵。这个矩阵每个格子要么是白，用字符'.'表示，要么是黑，用字符'#'表示。经过馍馍的分析，如果一张图片中包含一个特殊的 M X M的矩阵，那么这张图片可能包含病毒。我们称M X M的阵为"馍来检测病毒的超生逼特征矩阵”。现在告诉你一个N X N的图片矩阵，和一个M X M的“来检测病毒的超生逼特征矩阵”。你需要判断该图片是否包含病毒。即“模馍来检测病毒的超牛逼特征矩阵”通过平移可以完全重合在图片中的一个子矩阵里。

输入描述

第一行一个整数T(1 <= T <= 5)，表示测试数据的组数；

对于每组测试数据，第一行两个整数N, M(1 <= N，M <= 50)；

接下来N行，每行N个字符，用来描述待判断的图片A；

接下来M行，每行M个字符，用来描述”馍馍来检测病毒的超牛逼特征矩阵”。

输出描述

共T行，对于每组测试数据，如果包含，输出“Yes”，否则输出"No”(不包括引号)。

样例输入

2

3 2

#.#

.#.

#.#

#.

.#

4 1

....

....

....

....

#

样例输出

Yes

No

参考题解

枚举做法，枚举原矩阵的每个格子作为模版的左上角即可。然后再和原模版矩阵对比

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <cstdio>
#include <cstring>

const int N = 54;
char s[N][N], t[N][N];
int n, m;

bool solve() {
    scanf("%d %d", &n, &m);

    for (int i = 0; i < n; ++i)
        scanf("%s", s[i]);

    for (int i = 0; i < m; ++i)
        scanf("%s", t[i]);

    for (int x = 0; x + m - 1 < n; ++x) {
        for (int y = 0; y + m - 1 < n; ++y) {
            bool ok = true;
            for (int i = 0; i < m && ok; ++i) {
                for (int j = 0; j < m && ok; ++j) {
                    if (s[x + i][y + j] != t[i][j]) {
                        ok = false;
                    }
                }
            }
            if (ok) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        puts(solve() ? "Yes" : "No");
    }
    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Scanner;

public class Main {
    static final int N = 54;
    static char[][] s = new char[N][N];
    static char[][] t = new char[N][N];

    public static boolean solve() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        for (int i = 0; i < n; i++)
            s[i] = scanner.next().toCharArray();

        for (int i = 0; i < m; i++)
            t[i] = scanner.next().toCharArray();

        for (int x = 0; x + m - 1 < n; x++) {
            for (int y = 0; y + m - 1 < n; y++) {
                boolean ok = true;
                for (int i = 0; i < m && ok; i++) {
                    for (int j = 0; j < m && ok; j++) {
                        if (s[x + i][y + j] != t[i][j]) {
                            ok = false;
                        }
                    }
                }
                if (ok) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        while (T-- > 0) {
            System.out.println(solve() ? "Yes" : "No");
        }
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

def solve():
    n, m = map(int, input().split())
    s = [input() for _ in range(n)]
    t = [input() for _ in range(m)]

    for x in range(n - m + 1):
        for y in range(n - m + 1):
            ok = True
            for i in range(m):
                for j in range(m):
                    if s[x + i][y + j] != t[i][j]:
                        ok = False
                        break
                if not ok:
                    break
            if ok:
                return True
    return False

T = int(input())
for _ in range(T):
    print("Yes" if solve() else "No")