Advertisement
Milov

Percolation

Apr 12th, 2018
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.26 KB | None | 0 0
  1. n = input().split()
  2. k = int(n[1])
  3. razm = int(n[0])
  4.  
  5. graf = []
  6. met = []
  7.  
  8. for m in range(razm):
  9.     graf.append([])
  10.     met.append([])
  11.     for z in range(razm):
  12.         graf[m].append(1)
  13.         met[m].append(0)
  14.  
  15. for i in range(k):
  16.     s = input().split()
  17.     graf[int(s[0])][int(s[1])] = 0
  18.  
  19. for g in range(razm):
  20.     if graf[0][g] == 0:
  21.         h = 0
  22.         j = g
  23.         och = [[h, g]]
  24.         while och != []:
  25.             d = och.pop(0)
  26.             i = d[0]
  27.             j = d[1]
  28.             if i != razm - 1:
  29.                 if graf[i + 1][j] == 0 and met[i + 1][j] == 0:
  30.                     och.append([i + 1, j])
  31.                     met[i + 1][j] = 1
  32.             if i != 0:
  33.                 if graf[i - 1][j] == 0 and met[i - 1][j] == 0:
  34.                     och.append([i - 1, j])
  35.                     met[i - 1][j] = 1
  36.  
  37.             if j != razm - 1:
  38.                 if graf[i][j + 1] == 0 and met[i][j + 1] == 0:
  39.                     och.append([i, j + 1])
  40.                     met[i][j + 1] = 1
  41.  
  42.             if j != 0:
  43.                 if graf[i][j - 1] == 0 and met[i][j - 1] == 0:
  44.                     och.append([i, j - 1])
  45.                     met[i][j - 1] = 1
  46.  
  47. s = sum(met[razm-1])
  48.  
  49. if s == 0:
  50.     print('No')
  51. else:
  52.     print('Yes')
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement