#!/usr/bin/env python3 ''' R: number of cells of each edge of the grid, 2 <= R <= 20. N: ?? include the maximum length of the path requested, where 1 <= N < R3 - (R-1)3. A: the starting cell ID, assume this cell is located on one of the grid edges. B: the ID of the cell containing the honey, B != A. X: the number of wax-hardened cells, where 0 <= X < C - 1, followed by X integers on a single line Convert to 2-d grid, where parity of r+c always the same, for hex cells add border; BFS; output steps n <= N or 'No' ''' import sys nb = ((0, 2), (1, 1), (1, -1), (0, -2), (-1, -1), (-1, 1)) #neighbor directions def nbp(r, c, drc): # neighbor at offset drc dr, dc = drc return r+dr, c+dc def pg(): # debug: print grid for row in g: print(''.join(map(str, row))) def mapList(R): # return list of hex number n -> g location # What would be previous row in outer border sr, sc = 0, R+2 # left end coord dsr, dsc = 1, -1 # shift to start of next row ncLim = R-1 # # cells in row rc = [None] # numbering starts at 1 for _k in [0,1]: # top half, bottom for _i in range(R): # R rows sr += dsr # starting r, c shift sc += dsc ncLim -= dsc # length of row shifts r, c = sr, sc for _j in range(ncLim): rc.append((r,c)) c += 2 dsc = -dsc # shrink in second half return rc def set(code, val): r,c = rc[code] g[r][c] = val ##s = '2 6 2 6 3 4' ##s = '2 6 2 6 3 4 7' ##s = '4 6 2 31 5 11 12 13 20 21' ##s = '4 10 2 31 3 11 12 13' s = sys.stdin.read() (R, N, A, B, X, *hard) = map(int, s.split()) g = [([' '] if (R+r)%2 else []) + [1, ' ']*(2*R+1) for r in range(2*R+1)] # g[r][c] is 1 if (x+y-R) % 2 ==0 r, c = 0, R for drc in nb: # add boundary as sentinels for _i in range(R): g[r][c] = 0 r, c = nbp(r, c, drc) END = 2 rc = mapList(R) for i in hard + [A]: set(i, 0) set(B, END) edge = [rc[A]] n = 0 while edge: #BFS new = [] n += 1 for (r, c) in edge: for dr, dc in nb: rn, cn = r +dr, c + dc v = g[rn][cn] if v: if v == END: ## set(A, 'A') ## pg() print(n) sys.exit(0) g[rn][cn] = 0 new.append((rn, cn)) if n == N: break edge = new ## pg() print('No')