Advertisement
DimaT1

431

Aug 12th, 2016
113
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 3.25 KB | None | 0 0
  1. #-*-coding:utf8;-*-
  2. #qpy:3
  3. #qpy:console
  4.  
  5. def inpField(a):
  6.   flag = True
  7.   for i in a:
  8.     s = input()
  9.     for ch in s:
  10.       if   ch == ".":  i.append(-1)
  11.       elif ch == r'#': i.append(-2)
  12.       elif ch == "@":
  13.         if flag:
  14.           flag = False
  15.           i.append(0)
  16.         else:
  17.           i.append(-3)
  18.   return
  19.  
  20. def moveable(a, n, m, i, j):
  21.   _i = i + m[0]
  22.   _j = j + m[1]
  23.  
  24.   if (_i >= 0) and (_i < n):
  25.     if(_j >= 0) and (_j < n):
  26.       if (a[_i][_j] == -1) or (a[_i][_j] == -3):
  27.         # два способа дойти
  28.         __i = 0
  29.         __j = 0
  30.         f1 = True
  31.         while (__i != m[0]) and f1:
  32.           if m[0] < 0: __i-=1
  33.           else: __i+=1;
  34.           f1 = a[i+__i][j+__j] != -2
  35.         while (__j != m[1]) and f1:
  36.           if m[1] < 0: __j-=1
  37.           else: __j+=1;
  38.           #print("----------")
  39.           #print(i, j)
  40.           #print(_i, _j)
  41.           #print(str(i + __i) + " " + str(j + __j))
  42.           #print(__i, __j)
  43.           f1 = a[i+__i][j+__j] != -2
  44.         if f1: return True
  45.            
  46.         __i = 0
  47.         __j = 0
  48.         f1 = True
  49.         while (__j != m[1]) and f1:
  50.           if m[1] < 0: __j-=1
  51.           else: __j+=1;
  52.           f1 = a[i+__i][j+__j] != -2  
  53.         while (__i != m[0]) and f1:
  54.           if m[0] < 0: __i-=1
  55.           else: __i+=1;
  56.           f1 = a[i+__i][j+__j] != -2
  57.         if f1: return True
  58.   return False
  59.  
  60. def move(a, n, put, i, j, p):
  61.   key = False
  62.   res = False
  63.   I=-1
  64.   J=-1
  65.  
  66.   mask = [[-2, +1], [-1, +2], [+1, +2], [+2, +1], [+2, -1], [+1, -2], [-1, -2], [-2, -1]]
  67.   for m in mask:
  68.    
  69.     if moveable(a, n, m, i, j):
  70.       _i = i + m[0]
  71.       _j = j + m[1]
  72.       if (a[_i][_j] == -1) or (a[_i][_j] == -3):
  73.         if a[_i][_j] == -3:
  74.           key = True
  75.           I = _i
  76.           J = _j
  77.         res = True
  78.         a[_i][_j] = put
  79.         p[_i][_j] = [i, j]
  80.         #print(res, key, [I, J])
  81.   return [res, key, [I, J]]
  82.  
  83. def bfs(a, n, p):
  84.   flag = True
  85.   key = False
  86.   stage = 0
  87.   #global _buf
  88.   while flag:
  89.     flag = False
  90.     for i in range(n):
  91.       for j in range(n):
  92.         if a[i][j] == stage:
  93.           _buf = move(a, n, stage+1, i, j, p)
  94.           flag = flag or _buf[0]
  95.           if _buf[1]: stage+=1; return [True, stage, _buf[2]]
  96.     if flag: stage+= 1
  97.     #print(stage)
  98.     #for i in a:
  99.       #print(i)
  100.   return [False, stage, []]
  101.  
  102. def trace(_out, path, i, j, l):
  103.   while _out[i][j] != 0:
  104.     _out[i][j] = l
  105.     l-=1
  106.     i, j = path[i][j][0], path[i][j][1]
  107.     #print(str(i) + " " + str(j))
  108.   return
  109.  
  110. def listOut(a):
  111.   for i in a:
  112.     s = ""
  113.     for j in i:
  114.       if   j == -1:  s+= "."
  115.       elif j == -2:  s+= r"#"
  116.       else:          s+= "@"
  117.     print(s)
  118.   return
  119.  
  120. #****************
  121. n = int(input())
  122.  
  123. field = [[] for i in range(n)]
  124. p = [[[-1, -1] for i in range(n)] for i in range(n)]
  125. stage = 0
  126.  
  127. inpField(field)
  128.  
  129. buf = [[0 for i in range(n)] for i in range(n)]
  130. for i in range(n):
  131.   for j in range(n):
  132.     buf[i][j] = field[i][j]
  133.  
  134. res = bfs(field, n, p)
  135. #print(res)
  136. #for i in field:
  137.   #print(i)
  138.  
  139. #print(buf)
  140.  
  141. if res[0]:
  142.   trace(buf, p, res[2][0], res[2][1], res[1])
  143.   listOut(buf)
  144. else:
  145.   print("Impossible")
  146.  
  147.  
  148. '''
  149.  
  150. 5
  151. @..@.
  152. ..##.
  153. .....
  154. .....
  155. .....
  156.  
  157. '''
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement