首页 > 试题广场 >

小美的好矩阵

[编程题]小美的好矩阵

热度指数：2058 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小美定义一个矩阵是好矩阵，当且仅当该矩阵满足：
1. 矩阵仅由'A'、'B'、'C'三种字符组成。且三种字符都出现过。
2. 矩阵相邻的字符都不相等。

现在给定一个 $n*m$ 的矩阵，小美想知道有多少个3*3的子矩阵是好矩阵，你能帮帮她吗？

输入描述:

第一行输入两个整数，代表矩阵的行数和列数。
接下来的行，每行输入一个仅包含大写字母的长度为的字符串。

输出描述:

输出一个整数表示答案。

示例1

输入

4 4
DABC
ABAB
BABA
BBAB

输出

说明

有4个3*3的子矩阵。
左上角的子矩阵出现了'D'，因此不合法。
右上角的是好矩阵。
左下角的存在两个相邻的字母相同，因此不合法。
右下角的子矩阵里没有'C'，因此不合法。

算法知识视频讲解

Python

卷麻了

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2023/11/3 19:34
# @Author  : lanlin
# 小美的好矩阵


def judge33(matrix, y, x):
    result = True

    flag_x = [-1, 0, 1, -1, 0, 1, -1, 0, 1]
    flag_y = [-1, -1, -1, 0, 0, 0, 1, 1, 1]

    flag_ABC = set()
    for i in range(len(flag_y)):

        xx = x+flag_x[i]
        yy = y+flag_y[i]

        temp = matrix[yy][xx]

        # 判断三种字符是否都出现过，且没有其他字符
        if temp in ['A','B','C']:
            flag_ABC.add(temp)
        else:
            return False

        # 判断字符重复，每个元素只需判断其下、右两元素即可
        if (yy+1)<(y+2) and temp == matrix[yy+1][xx]:
            return False
        if (xx+1)<(x+2) and temp == matrix[yy][xx+1]:
            return False

    if len(flag_ABC) != 3:
        result = False

    return result


def judge(data, m, n):
    result = 0
    for y in range(m-2):
        for x in range(n-2):
            if judge33(data, y+1, x+1):
                result += 1
    return result


if __name__=='__main__':
    array1 = input().split(" ")
    m = int(array1[0])
    n = int(array1[1])

    data_array = []

    for i in range(m):
        temp_list = list(input())
        data_array.append(temp_list)

    print(judge(data_array, m, n))

'''
4 4
DABC
ABAB
BABA
BBAB
'''

将矩阵化成一个一个的小块，然后根据题目要求进行判断，注意行列顺序

发表于 2023-11-03 22:01:15 回复(0)

Python

秋招早日上岸

将矩阵化成一个一个的小块，然后根据题目要求进行判断

from collections import Counter

def isGoodMatrix(mtx,idx,idy):
    arr = []
    for i in range(3):
        for j in range(3):
            arr.append(mtx[idx+i][idy+j])
            # 判断条件二 矩阵相邻的字符都不相等。
            if i<2:
                if mtx[idx+i][idy+j] == mtx[idx+i+1][idy+j]:
                    return False
            if j<2:
                if mtx[idx+i][idy+j] == mtx[idx+i][idy+j+1]:
                    return False   
    # 判断条件一 矩阵仅由'A'、'B'、'C'三种字符组成。且三种字符都出现过。        
    temp = set(arr)
    if len(temp)!=3&nbs***bsp;'A' not in temp&nbs***bsp;'B' not in temp&nbs***bsp;'C' not in temp:
        return False    
    return True

def sol(n,m,mat):
    if n<3&nbs***bsp;m<3: return 0
    ans = 0
    for i in range(n-2):
        for j in range(m-2):
            if isGoodMatrix(mat,i,j):
                ans += 1
    return ans

while 1:
    try:
        n,m  = map(int,input().split())
        arr = []
        for i in range(n):
            s = input().strip()
            arr.append([x for x in s])
        ans = sol(n,m,arr)
        print(ans)

    except:
        break

编辑于 2023-10-21 04:12:52 回复(0)

Python

牛客589178787号

n,m=[int(i) for i in input().split(' ')]
matrix=[]

for i in range(n):
    matrix.append([j for j in input()])

def judge(matrix, row, col):
    uni_ch=set()
    for x in range(row,row+3):
        for y in range(col,col+3):
            ch=matrix[x][y]
            uni_ch.add(ch)
            if ch >= 'D'&nbs***bsp;(y + 1 < col + 3 and ch == matrix[x][y + 1])&nbs***bsp;(x + 1 < row + 3 and ch == matrix[x + 1][y]):
                return False
    return len(uni_ch)==3
res=0
for i in range(0,n-2):
    for j in range(0,m-2):
        if judge(matrix,i,j):
            res+=1
print(res)

编辑于 2023-10-19 11:23:58 回复(2)

提交观点

问题信息

来自：2023年美团秋招编程...

难度：

3条回答 42收藏 2285浏览

小美的好矩阵

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题