考え方
原点から$\sqrt{M}$の距離にある点を求めておけば，任意の点についても原点をずらすだけで$\sqrt{M}$の距離にある点が求まる．半径$r$の円周上の格子点の個数は$2\pi r$以下なので，高々$O(N)$個．よって，全ての点を1回ずつみながら遷移すると$O(N^{3})$．
以上より，BFSで最短距離を求めればよい．
（参考：最短経路問題 - 競プロはじめました）
回答例
from collections import deque N, M = map(int, input().split()) dp = [[-1] * N for _ in range(N)] dp[0][0] = 0 memo = [] for i in range(N): for j in range(N): if i ** 2 + j ** 2 == M: memo.append((i, j)) memo.append((-i, j)) memo.append((i, -j)) memo.append((-i, -j)) q = deque([(0, 0)]) while q: cx, cy = q.popleft() for dx, dy in memo: nx, ny = cx + dx, cy + dy if ((not 0 <= nx < N) or (not 0 <= ny < N)): continue if dp[nx][ny] > -1: continue dp[nx][ny] = dp[cx][cy] + 1 q.append((nx, ny)) for i in range(N): print(*dp[i])
