Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def valid(y,x):
- if y>=0 and x>=0 and y<N and x<horizontal_len: #this is not to get out of range right
- return True
- def find_blocks(y,x):
- Q.append(y) # cant get why append x and y right from the start
- Q.append(x)
- #search around 4 directions (up, right, left, down)
- dy = [0,1,0,-1] #cant make sence of this. please explain.
- dx = [1,0,-1,0]
- # if nothing is in Q then terminate counting block
- while Q:
- y = Q.pop(0) # if i get it - this will run as long as theres 1s to append. when 0s are found Q will become empty and thus end the block, add 1 to the sum of blocks and the whole thing will start scaning for 1 again.
- 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())) #you are using map() and for loop to create the matrix. what is the difference with my approach?
- matrix.append(row)
- #row length
- horizontal_len = len(matrix[0]) #this is for better understanding of the logic but the nested for loop can be done without this
- 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 #scans untill finds 1 and then starts the function
- if matrix[start_y][start_x] == 1:
- #make 1s to -1 for not to calculate again. # if its not -1 its gonna calculate the same blocks over and over again
- matrix[start_y][start_x] = -1
- Q=[]
- #start function
- find_blocks(start_y, start_x)
- blocks +=1
- print(blocks)
- # Havent gotten to algorithms yet(still learning fundamentals - lists, tuples, functions) so don't know what BFS is at all. Any info will be great.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement