Advertisement
Guest User

Untitled

a guest
May 20th, 2018
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.17 KB | None | 0 0
  1. from collections import deque
  2.  
  3.  
  4. def bfs(g, st):
  5. global used, n, m
  6. queue = deque([st])
  7. used[st[0]][st[1]] = True
  8. while len(queue) != 0:
  9. v = queue.popleft()
  10. p = []
  11. if v[0] < n - 1 and g[v[0] + 1][v[1]] != g[v[0]][v[1]]:
  12. p.append((v[0] + 1, v[1]))
  13. if v[0] > 0 and g[v[0] - 1][v[1]] != g[v[0]][v[1]]:
  14. p.append((v[0] - 1, v[1]))
  15. if v[1] < m - 1 and g[v[0]][v[1] + 1] != g[v[0]][v[1]]:
  16. p.append((v[0], v[1] + 1))
  17. if v[1] > 0 and g[v[0]][v[1] - 1] != g[v[0]][v[1]]:
  18. p.append((v[0], v[1] - 1))
  19. for u in p:
  20. if not used[u[0]][u[1]]:
  21. queue.append(u)
  22. used[u[0]][u[1]] = True
  23. return
  24.  
  25. fin = open("chessboard.in", "r")
  26. fout = open("chessboard.out", "w")
  27. n, m = map(int, fin.readline().split())
  28. lst = []
  29. used = []
  30. for i in range(n):
  31. s = fin.readline().rstrip()
  32. lst.append([])
  33. used.append([False] * m)
  34. for j in s:
  35. lst[-1].append(j)
  36. ans = 0
  37.  
  38. for i in range(n):
  39. for j in range(m):
  40. if not used[i][j]:
  41. bfs(lst, (i, j))
  42. ans += 1
  43.  
  44. print(ans, file=fout)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement