Advertisement
simeonshopov

Find the blocks

Dec 9th, 2019
181
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.17 KB | None | 0 0
  1. def valid(y,x):
  2.     if y>=0 and x>=0 and y<N and x<horizontal_len:  #this is not to get out of range right
  3.         return True
  4.  
  5. def find_blocks(y,x):
  6.     Q.append(y) # cant get why append x and y right from the start
  7.     Q.append(x)
  8.  
  9.     #search around 4 directions (up, right, left, down)
  10.     dy = [0,1,0,-1] #cant make sence of this. please explain.
  11.     dx = [1,0,-1,0]
  12.  
  13.     # if nothing is in Q then terminate counting block
  14.     while Q:
  15.         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.
  16.         x = Q.pop(0)
  17.  
  18.         for dir in range(len(dy)):
  19.             next_y = y + dy[dir]
  20.             next_x = x + dx[dir]
  21.  
  22.             #if around component is valid range(inside the matrix) and it is 1(not 0) then include it as a part of block
  23.             if valid(next_y,next_x) and matrix[next_y][next_x] == 1:
  24.                 Q.append(next_y)
  25.                 Q.append(next_x)
  26.                 matrix[next_y][next_x] = -1
  27.  
  28.  
  29. N = int(input())
  30.  
  31. matrix = []
  32. for rows in range(N):
  33.    row = list(map(int, input().split()))  #you are using map() and for loop to create the matrix. what is the difference with my approach?
  34.    matrix.append(row)
  35.  
  36. #row length
  37. horizontal_len = len(matrix[0]) #this is for better understanding of the logic but the nested for loop can be done without this
  38.  
  39. blocks = 0
  40.  
  41. #search from matrix[0][0] to matrix[N][horizontal_len]
  42. for start_y in range(N):
  43.     for start_x in range(horizontal_len):
  44.  
  45.         #if a number is 1 then start calculating #scans untill finds 1 and then starts the function
  46.         if matrix[start_y][start_x] == 1:
  47.             #make 1s to -1 for not to calculate again. # if its not -1 its gonna calculate the same blocks over and over again
  48.             matrix[start_y][start_x] = -1
  49.             Q=[]
  50.  
  51.             #start function
  52.             find_blocks(start_y, start_x)
  53.             blocks +=1
  54.  
  55. print(blocks)
  56. # 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