import sequtils,times#,nimprof type Pos = tuple[x,y:int16] template stopwatch(body) = (let t1 = cpuTime();body;stderr.writeline "TIME:",(cpuTime() - t1) * 1000,"ms") proc getchar_unlocked():char {. importc:"getchar_unlocked",header: "" .} proc scan(): int = while true: let k = getchar_unlocked() if k < '0': return result = 10 * result + k.ord - '0'.ord let h = scan() let w = scan() var M : array[500,array[500,bool]] const INF = int16.high var DP : array[500,array[500,array[2,int16]]] var s : Pos var g : Pos for y in 0.. 0: let qe = Q.dequeue() let x = cast[int16](qe shr 48) let y = cast[int16](qe shr 32) let isKnight = cast[int16](qe shr 16) let diff = cast[int16](qe) let nextDiff = diff + 1 if abs(x - w) > 100 and abs(y - h) > 100 and 3 < x and x < w - 4 and 3 < y and y < h - 4: for i in 0..<(1 + isKnight): let nx = x + D2[isKnight][i].x let ny = y + D2[isKnight][i].y if nx == g.x and ny == g.y : echo nextDiff + INF return true let nextIsKnight = if M[nx][ny]: 1 - isKnight else: isKnight if DP[nx][ny][nextIsKnight] <= nextDiff: continue DP[nx][ny][nextIsKnight] = nextDiff Q.enqueue(en(nx,ny,nextIsKnight,nextDiff)) else: for i in 0..<(4 + isKnight * 4): let nx = x + D[isKnight][i].x let ny = y + D[isKnight][i].y if nx < 0 or ny < 0 or nx >= w or ny >= h : continue if nx == g.x and ny == g.y : echo nextDiff + INF return true let nextIsKnight = if M[nx][ny]: 1 - isKnight else: isKnight if DP[nx][ny][nextIsKnight] <= nextDiff: continue DP[nx][ny][nextIsKnight] = nextDiff Q.enqueue(en(nx,ny,nextIsKnight,nextDiff)) return false if not solve(): echo -1