时间戳

首页 > 解决方案 > 找到所有的块

python - 找到所有的块

问题描述

我对 python 和编码非常陌生。我有这个作业要做：

您将在第一行收到矩阵 (n) 的行，在接下来的 n 行中，您将收到矩阵的每一行作为字符串（零和一个由单个空格分隔）。您必须计算您有多少块（水平或对角连接的块）以下是示例：

Input:
5
1 1 0 0 0
1 1 0 0 0
0 0 0 0 0
0 0 0 1 1
0 0 0 1 1
Output:
2

Input:
6
1 1 0 1 0 1
0 1 1 1 1 1
0 1 0 0 0 0
0 1 1 0 0 0
0 1 1 1 1 0
0 0 0 1 1 0
Output:
1

Input:
4
0 1 0 1 1 0
1 0 1 1 0 1
1 0 0 0 0 0
0 0 0 1 0 0
Output:
5

我现在想出的代码是：

n = int(input())
blocks = 0

matrix = [[int(i) for i in input().split()] for j in range(n)]

#loop or something to find the blocks in the matrix

print(blocks)

任何帮助将不胜感激。

标签： pythonlistnested

解决方案

def valid(y,x):
    if y>=0 and x>=0 and y<N and x<horizontal_len:
        return True

def find_blocks(y,x):
    Q.append(y)
    Q.append(x)

    #search around 4 directions (up, right, left, down)
    dy = [0,1,0,-1]
    dx = [1,0,-1,0]

    # if nothing is in Q then terminate counting block
    while Q:
        y = Q.pop(0)
        x = Q.pop(0)

        for dir in range(len(dy)):
            next_y = y + dy[dir]
            next_x = x + dx[dir]

            #if around component is valid range(inside the matrix) and it is 1(not 0) then include it as a part of block
            if valid(next_y,next_x) and matrix[next_y][next_x] == 1:
                Q.append(next_y)
                Q.append(next_x)
                matrix[next_y][next_x] = -1


N = int(input())

matrix = []
for rows in range(N):
   row = list(map(int, input().split()))
   matrix.append(row)

#row length
horizontal_len = len(matrix[0])

blocks = 0

#search from matrix[0][0] to matrix[N][horizontal_len]
for start_y in range(N):
    for start_x in range(horizontal_len):

        #if a number is 1 then start calculating
        if matrix[start_y][start_x] == 1:
            #make 1s to -1 for not to calculate again
            matrix[start_y][start_x] = -1
            Q=[]

            #start function
            find_blocks(start_y, start_x)
            blocks +=1

print(blocks)

我使用 BFS 算法来解决这个问题。引用可能不足以理解逻辑。如果您对此解决方案有任何疑问，请告诉我！

推荐阅读