「数 \(x\) が書かれたマスと数 \(y\) が書かれたマスは隣り合っているか？」を \((x,y)\) それぞれについて調べると、\(\Omega((HW)^2)\) 時間かかってしまい TLE します。隣り合っているマスの組合せを直接調べましょう。

それぞれのマスは上下左右の最大 \(4\) つのマスに隣接しています。これらを全て調べ、\(x<y\) の条件・重複・出力順に注意することで問題を解くことができます。計算量は \(O(HW\log HW)\) です。

実際には、それぞれのマスについて、右と下のマスのみを調べることで、重複なく隣り合うマスの組を調べることができます

実装例(Python)

H,W=map(int,input().split())
A=[list(map(int,input().split())) for _ in range(H)]

ans=[]
for i in range(H):
  for j in range(W):
    if i+1<H:
      x=min(A[i][j],A[i+1][j])
      y=max(A[i][j],A[i+1][j])
      ans.append((x,y))
    if j+1<W:
      x=min(A[i][j],A[i][j+1])
      y=max(A[i][j],A[i][j+1])
      ans.append((x,y))

ans.sort()
for p in ans:
  print(*p)