Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #-*-coding:utf8;-*-
- #qpy:3
- #qpy:console
- def inpField(a):
- flag = True
- for i in a:
- s = input()
- for ch in s:
- if ch == ".": i.append(-1)
- elif ch == r'#': i.append(-2)
- elif ch == "@":
- if flag:
- flag = False
- i.append(0)
- else:
- i.append(-3)
- return
- def moveable(a, n, m, i, j):
- _i = i + m[0]
- _j = j + m[1]
- if (_i >= 0) and (_i < n):
- if(_j >= 0) and (_j < n):
- if (a[_i][_j] == -1) or (a[_i][_j] == -3):
- # два способа дойти
- __i = 0
- __j = 0
- f1 = True
- while (__i != m[0]) and f1:
- if m[0] < 0: __i-=1
- else: __i+=1;
- f1 = a[i+__i][j+__j] != -2
- while (__j != m[1]) and f1:
- if m[1] < 0: __j-=1
- else: __j+=1;
- #print("----------")
- #print(i, j)
- #print(_i, _j)
- #print(str(i + __i) + " " + str(j + __j))
- #print(__i, __j)
- f1 = a[i+__i][j+__j] != -2
- if f1: return True
- __i = 0
- __j = 0
- f1 = True
- while (__j != m[1]) and f1:
- if m[1] < 0: __j-=1
- else: __j+=1;
- f1 = a[i+__i][j+__j] != -2
- while (__i != m[0]) and f1:
- if m[0] < 0: __i-=1
- else: __i+=1;
- f1 = a[i+__i][j+__j] != -2
- if f1: return True
- return False
- def move(a, n, put, i, j, p):
- key = False
- res = False
- I=-1
- J=-1
- mask = [[-2, +1], [-1, +2], [+1, +2], [+2, +1], [+2, -1], [+1, -2], [-1, -2], [-2, -1]]
- for m in mask:
- if moveable(a, n, m, i, j):
- _i = i + m[0]
- _j = j + m[1]
- if (a[_i][_j] == -1) or (a[_i][_j] == -3):
- if a[_i][_j] == -3:
- key = True
- I = _i
- J = _j
- res = True
- a[_i][_j] = put
- p[_i][_j] = [i, j]
- #print(res, key, [I, J])
- return [res, key, [I, J]]
- def bfs(a, n, p):
- flag = True
- key = False
- stage = 0
- #global _buf
- while flag:
- flag = False
- for i in range(n):
- for j in range(n):
- if a[i][j] == stage:
- _buf = move(a, n, stage+1, i, j, p)
- flag = flag or _buf[0]
- if _buf[1]: stage+=1; return [True, stage, _buf[2]]
- if flag: stage+= 1
- #print(stage)
- #for i in a:
- #print(i)
- return [False, stage, []]
- def trace(_out, path, i, j, l):
- while _out[i][j] != 0:
- _out[i][j] = l
- l-=1
- i, j = path[i][j][0], path[i][j][1]
- #print(str(i) + " " + str(j))
- return
- def listOut(a):
- for i in a:
- s = ""
- for j in i:
- if j == -1: s+= "."
- elif j == -2: s+= r"#"
- else: s+= "@"
- print(s)
- return
- #****************
- n = int(input())
- field = [[] for i in range(n)]
- p = [[[-1, -1] for i in range(n)] for i in range(n)]
- stage = 0
- inpField(field)
- buf = [[0 for i in range(n)] for i in range(n)]
- for i in range(n):
- for j in range(n):
- buf[i][j] = field[i][j]
- res = bfs(field, n, p)
- #print(res)
- #for i in field:
- #print(i)
- #print(buf)
- if res[0]:
- trace(buf, p, res[2][0], res[2][1], res[1])
- listOut(buf)
- else:
- print("Impossible")
- '''
- 5
- @..@.
- ..##.
- .....
- .....
- .....
- '''
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement