| 4 | from itertools import product |
| 5 | |
| 6 | def bfs(m: list[list[tuple[str,int]]], rs: int, cs: int, enemy: str) -> tuple[int,int] | None: |
| 7 | q, parentmap = deque([(rs,cs)]), {(rs,cs): (-1,-1)} |
| 8 | while q: |
| 9 | r,c = q.popleft() |
| 10 | if m[r][c][0] == enemy: |
| 11 | while parentmap[r,c] != (rs,cs): |
| 12 | r,c = parentmap[r,c] |
| 13 | return r,c |
| 14 | for rr,cc in [(r-1,c),(r,c-1),(r,c+1),(r+1,c)]: |
| 15 | if (rr,cc) in parentmap or m[rr][cc][0] not in ['.',enemy]: |
| 16 | continue |
| 17 | q.append((rr,cc)) |
| 18 | parentmap[rr,cc] = (r,c) |
| 19 | return None |
| 20 | |
| 21 | def get_target(m: list[list[tuple[str,int]]], r: int, c: int, enemy: str) -> tuple[int,int] | None: |
| 22 | minhp, rt, ct = 1000, None, None |