Advertisement
Guest User

Untitled

a guest
Oct 12th, 2017
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.32 KB | None | 0 0
  1. def check(matr, i, j):
  2.     if i < 0 or j < 0 or j >= len(matr) or i >= len(matr) or matr[i][j] == 1:
  3.         return False
  4.     return True
  5.  
  6. def bfs(matr, sX, sY, fX, fY):
  7.     dy = [2, 2, 1, 1, -1, -1, -2, -2]
  8.     dx = [1, -1, 2, -2, 2, -2, 1, -1]
  9.     currx = sX
  10.     curry = sY
  11.     queue = []
  12.     for i in range(len(dy)):
  13.         newx = currx + dx[i]
  14.         newy = curry + dy[i]
  15.         if (check(matr, newx, newy)):
  16.             matr[newx][newy] = 1
  17.             queue.append(newx)
  18.             queue.append(newy)
  19.             queue.append(1)
  20.     while len(queue) > 0:
  21.         currx = queue[0]
  22.         curry = queue[1]
  23.         cnt = queue[2]
  24.         if currx == fX and curry == fY:
  25.             return cnt
  26.         queue.pop(0)
  27.         queue.pop(0)
  28.         queue.pop(0)
  29.         for i in range(len(dy)):
  30.             newx = currx + dx[i]
  31.             newy = curry + dy[i]
  32.             if (check(matr, newx, newy)):
  33.                 matr[newx][newy] = 1
  34.                 queue.append(newx)
  35.                 queue.append(newy)
  36.                 queue.append(cnt + 1)
  37.  
  38. n = int(input())
  39. matr = [[0 for x in range(n)] for i in range(n)] #???
  40. sX, sY = map(int, input().split())
  41. sX -= 1
  42. sY -= 1
  43. fX, fY = map(int, input().split())
  44. fX -= 1
  45. fY -= 1
  46. if sX == fX and sY == fY:
  47.     print(0)
  48. else:
  49.     print(bfs(matr, sX, sY, fX, fY))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement