返回目录

题目描述

给定一个矩阵，包含 N * M 个整数，和一个包含 K 个整数的数组。

现在要求在这个矩阵中找一个宽度最小的子矩阵，要求子矩阵包含数组中所有的整数。

输入描述

第一行输入两个正整数 N，M，表示矩阵大小。

接下来 N 行 M 列表示矩阵内容。

下一行包含一个正整数 K。

下一行包含 K 个整数，表示所需包含的数组，K 个整数可能存在重复数字。

所有输入数据小于1000。

输出描述

输出包含一个整数，表示满足要求子矩阵的最小宽度，若找不到，输出-1。

示例：

Python算法源码

# 检查矩阵的指定列区间是否包含所有要求的整数
def contains_all(matrix, left, right, required_nums):
    count_map = {} # 使用字典记录每个要求整数的数量
    for num in required_nums: # 初始化要求整数的数量
        count_map[num] = count_map.get(num, 0) + 1
  
    for row in matrix: # 遍历矩阵的每一行
        for j in range(left, right + 1): # 遍历指定的列区间
            if row[j] in count_map: # 如果当前元素是要求的整数之一
                count_map[row[j]] -= 1 # 减少字典中对应整数的数量
                if count_map[row[j]] == 0: # 如果某个整数的数量减少到0
                    del count_map[row[j]] # 从字典中移除该整数
    return not count_map # 如果字典为空，则表示所有要求的整数都包含在内

# 寻找最小宽度子矩阵的方法
def find_min_width_submatrix(matrix, required_nums):
    min_width = float('inf') # 设置最小宽度初始值为正无穷
    for left in range(len(matrix[0])): # 遍历所有可能的左边界
        for right in range(left, len(matrix[0])): # 遍历所有可能的右边界
            if contains_all(matrix, left, right, required_nums): # 检查当前列区间是否包含所有要求的整数
                min_width = min(min_width, right - left + 1) # 更新最小宽度
    return min_width if min_width != float('inf') else -1 # 如果找到符合条件的子矩阵，返回最小宽度；否则返回-1

if __name__ == "__main__":
    N, M = map(int, input().split()) # 读取行数和列数
    matrix = [list(map(int, input().split())) for _ in range(N)] # 读取矩阵

    K = int(input()) # 要包含的整数数组的长度
    required_nums = list(map(int, input().split())) # 读取要包含的整数数组

    print(find_min_width_submatrix(matrix, required_nums)) # 输出找到的最小宽度子矩阵的宽度

C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// 检查矩阵的指定列区间是否包含所有要求的整数
int containsAll(const int** matrix, int rows, int cols, int left, int right, const int* requiredNums, int requiredLength) {
    int* countMap = (int*)malloc((requiredLength + 1) * sizeof(int)); // 使用数组记录每个要求整数的数量
    if (countMap == NULL) {
        return 0; // 内存分配失败
    }
  
    for (int i = 0; i <= requiredLength; ++i) { // 初始化要求整数的数量
        countMap[i] = 0;
    }
  
    for (int i = 0; i < requiredLength; ++i) { // 更新要求整数的数量
        countMap[requiredNums[i]]++;
    }
  
    for (int i = 0; i < rows; ++i) { // 遍历矩阵的每一行
        for (int j = left; j <= right; ++j) { // 遍历指定的列区间
            int num = matrix[i][j];
            if (num >= 0 && num <= requiredLength && countMap[num] > 0) { // 如果当前元素是要求的整数之一
                countMap[num]--; // 减少数组中对应整数的数量
            }
        }
    }
  
    for (int i = 0; i <= requiredLength; ++i) { // 检查所有要求的整数的数量是否为0
        if (countMap[i] != 0) {
            free(countMap);
            return 0; // 不包含所有要求的整数
        }
    }
  
    free(countMap);
    return 1; // 包含所有要求的整数
}

// 寻找最小宽度子矩阵的方法
int findMinWidthSubmatrix(const int** matrix, int rows, int cols, const int* requiredNums, int requiredLength) {
    int minWidth = INT_MAX; // 设置最小宽度初始值为最大整数
    for (int left = 0; left < cols; ++left) { // 遍历所有可能的左边界
        for (int right = left; right < cols; ++right) { // 遍历所有可能的右边界
            if (containsAll(matrix, rows, cols, left, right, requiredNums, requiredLength)) { // 检查当前列区间是否包含所有要求的整数
                int width = right - left + 1;
                if (width < minWidth) { // 更新最小宽度
                    minWidth = width;
                }
            }
        }
    }
    return (minWidth == INT_MAX) ? -1 : minWidth; // 如果找到符合条件的子矩阵，返回最小宽度；否则返回-1
}

int main() {
    int N, M; // 矩阵的行数和列数
    scanf("%d %d", &N, &M); // 读取行数和列数
    int** matrix = (int**)malloc(N * sizeof(int*)); // 初始化矩阵
    for (int i = 0; i < N; ++i) { // 读取矩阵中的每个元素
        matrix[i] = (int*)malloc(M * sizeof(int));
        for (int j = 0; j < M; ++j) {
            scanf("%d", &matrix[i][j]);
        }
    }
  
    int K; // 要包含的整数数组的长度
    scanf("%d", &K); // 读取长度
    int* requiredNums = (int*)malloc(K * sizeof(int)); // 初始化要包含的整数数组
    for (int i = 0; i < K; ++i) { // 读取要包含的整数
        scanf("%d", &requiredNums[i]);
    }
  
    int result = findMinWidthSubmatrix((const int**)matrix, N, M, requiredNums, K); // 输出找到的最小宽度子矩阵的宽度
    printf("%d\n", result);
  
    for (int i = 0; i < N; ++i) { // 释放矩阵的内存
        free(matrix[i]);
    }
    free(matrix);
    free(requiredNums);
  
    return 0;
}

Java算法源码

import java.util.*;

public class Main {
    // 检查矩阵的指定列区间是否包含所有要求的整数
    static boolean containsAll(int[][] matrix, int left, int right, int[] requiredNums) {
        Map<Integer, Integer> countMap = new HashMap<>(); // 使用哈希表记录每个要求整数的数量

        // 初始化要求整数的数量
        for (int num : requiredNums) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }

        // 遍历矩阵的每一行
        for (int[] row : matrix) {
            // 遍历指定的列区间
            for (int j = left; j <= right; ++j) {
                int num = row[j];
                if (countMap.containsKey(num)) { // 如果当前元素是要求的整数之一
                    countMap.put(num, countMap.get(num) - 1); // 减少哈希表中对应整数的数量
                    if (countMap.get(num) == 0) { // 如果某个整数的数量减少到0
                        countMap.remove(num); // 从哈希表中移除该整数
                    }
                }
            }
        }
        return countMap.isEmpty(); // 如果哈希表为空，则表示所有要求的整数都包含在内
    }

    // 寻找最小宽度子矩阵的方法
    static int findMinWidthSubmatrix(int[][] matrix, int[] requiredNums) {
        int minWidth = Integer.MAX_VALUE; // 设置最小宽度初始值为最大整数
        int rows = matrix.length;
        int cols = matrix[0].length;

        // 遍历所有可能的左边界
        for (int left = 0; left < cols; ++left) {
            // 遍历所有可能的右边界
            for (int right = left; right < cols; ++right) {
                // 检查当前列区间是否包含所有要求的整数
                if (containsAll(matrix, left, right, requiredNums)) {
                    minWidth = Math.min(minWidth, right - left + 1); // 更新最小宽度
                }
            }
        }
        return (minWidth == Integer.MAX_VALUE) ? -1 : minWidth; // 如果找到符合条件的子矩阵，返回最小宽度；否则返回-1
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt(); // 矩阵的行数
        int M = scanner.nextInt(); // 矩阵的列数
        int[][] matrix = new int[N][M]; // 初始化矩阵

        // 读取矩阵中的每个元素
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < M; ++j) {
                matrix[i][j] = scanner.nextInt();
            }
        }

        int K = scanner.nextInt(); // 要包含的整数数组的长度
        int[] requiredNums = new int[K]; // 初始化要包含的整数数组

        // 读取要包含的整数
        for (int i = 0; i < K; ++i) {
            requiredNums[i] = scanner.nextInt();
        }

        // 输出找到的最小宽度子矩阵的宽度
        System.out.println(findMinWidthSubmatrix(matrix, requiredNums));
    }
}