import bisect, heapq, sys, math, copy, itertools, decimal
from collections import defaultdict, deque
import pprint
from typing import Iterable, List, Tuple
import numpy as np
sys.setrecursionlimit(10**7)
def INT(): return int(input())
def MI(d=0): return map(lambda x:int(x)+d, input().split())
def MS(): return map(str, input().split())
def LI(d=0): return list(map(lambda x:int(x)+d, input().split()))
def LS(): return list(map(str, input().split()))
def pr_line(itr): print(*itr, sep='\n')
def pr_mtx(matrix): [print(*row) for row in matrix]
def pr_mtx2(matrix, l=2):
for row in matrix:
for x in row:
print(str(x).rjust(l), end='')
print('\n')
def pr_stderr(*s): print(*s, file=sys.stderr)
dij = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dij2 = [[1, 0], [0, 1], [-1, 0], [0, -1], [1, 1], [1, -1], [-1, 1], [-1, -1]]
INF = float('inf')
from time import time
base_ms = 0
def tic():
global base_ms
base_ms = time()
def toc():
now = time()
return (now - base_ms) * 1000
###########################################################
# input
N = INT()
A = [LI() for _ in range(N)]
###########################################################
Coord = Tuple[int, int]
###########################################################
def score(tour: Iterable[Tuple[int, int]]) -> int:
s = 0
for i, (r, c) in enumerate(tour):
s += A[r][c] * (i + 1)
return s
def cheb_adj(a: Coord, b: Coord) -> bool:
return max(abs(a[0] - b[0]), abs(a[1] - b[1])) == 1
def snake_coords(h: int, w: int) -> List[Coord]:
"""h×w を行ごと往復で走査する座標, ローカル"""
res = []
for r in range(h):
if r % 2 == 0:
for c in range(w):
res.append((r, c))
else:
for c in range(w - 1, -1, -1):
res.append((r, c))
return res
def two_row_bundle_path(n: int, t: int) -> List[Coord]:
"""
2行ずつ束ねて走査するハミルトン路を返す。
出力は(0-index)。
"""
assert n % 2 == 0
path: List[Coord] = []
visited = [[False] * n for _ in range(n)]
for r in range(0, n, 2):
si, sj = transform_point((r, 0), n, n, t)
path.append((si, sj))
visited[si][sj] = True
for c in range(1, n):
i1, j1 = transform_point((r, c), n, n, t)
i2, j2 = transform_point((r+1, c), n, n, t)
if A[i1][j1] < A[i2][j2]:
path.append((i1, j1))
visited[i1][j1] = True
else:
path.append((i2, j2))
visited[i2][j2] = True
for c in range(n - 1, -1, -1):
i1, j1 = transform_point((r, c), n, n, t)
i2, j2 = transform_point((r+1, c), n, n, t)
if not visited[i1][j1]:
path.append((i1, j1))
visited[i1][j1] = True
if not visited[i2][j2]:
path.append((i2, j2))
visited[i2][j2] = True
return path
def transform_point(rc: Coord, h: int, w: int, t: int) -> Coord:
"""
h×w のグリッド上の1点 (r,c) を 8通り (D4) で変換する。
t in [0..7]
0: identity
1: rot90
2: rot180
3: rot270
4: flipH (左右反転)
5: flipH + rot90
6: flipH + rot180
7: flipH + rot270
"""
r, c = rc
rr, cc = r, c
if t >= 4:
cc = (w - 1) - cc # horizontal flip
k = t % 4
if k == 0:
return (rr, cc)
elif k == 1:
# (r,c) in h×w -> (c, h-1-r) in w×h
return (cc, (h - 1) - rr)
elif k == 2:
return ((h - 1) - rr, (w - 1) - cc)
else: # k == 3
return ((w - 1) - cc, rr)
def block_order(nb_r: int, nb_c: int) -> List[Coord]:
"""ブロック座標(Br,Bc)を牛耕式で並べる"""
order = []
for br in range(0, nb_r, 2):
for bc in range(nb_c):
order.append((br, bc))
for bc in range(nb_c - 1, -1, -1):
order.append((br + 1, bc))
return order
def eval_block_local_score(local_path: List[Coord], A: List[List[int]], base_i: int, base_j: int, k0: int) -> int:
"""
ブロック内だけの寄与を評価（絶対kを使う）。
local_path はブロック内ローカル座標列。
"""
s = 0
for dk, (r, c) in enumerate(local_path):
s += (k0 + dk) * A[base_i + r][base_j + c]
return s
def main() -> List[Coord]:
B = 10 # ブロックサイズ（要調整）
assert N % B == 0
nb_r = N // B
nb_c = N // B
base_local = snake_coords(B, B) # B×B の基本牛耕
order = block_order(nb_r, nb_c)
path: List[Coord] = []
prev: Coord | None = None
k = 0
# for idx, (br, bc) in enumerate(order):
# bi = br * B
# bj = bc * B
# best_local = None
# best_score = None
# # 8通りの向きを試す
# for t in range(8):
# local = transform(base_local, B, B, t)
# first_abs = (bi + local[0][0], bj + local[0][1])
# if prev is not None and not cheb_adj(prev, first_abs):
# continue # 入り口が繋がらない
# sc = eval_block_local_score(local, A, bi, bj, k)
# if best_score is None or sc > best_score:
# best_score = sc
# best_local = local
# # どれも繋がらない場合は、保険で「前ブロックの最後と隣接するマス」を先頭にするよう調整が要るが、
# # B×B正方形＆ブロック牛耕なら通常は繋がる向きが見つかるはず。
# if best_local is None:
# # フォールバック：繋がり無視でそのまま（最悪不正になるので、本来はここを潰すべき）
# best_local = base_local
# # 追加
# for (r, c) in best_local:
# path.append((bi + r, bj + c))
# prev = path[-1]
# k += B * B
# 念のため、逆順も比較（開始終了自由なので逆順も合法）
def total_score(p: List[Coord]) -> int:
s = 0
for kk, (i, j) in enumerate(p):
s += kk * A[i][j]
return s
p_rev = list(reversed(path))
if total_score(p_rev) > total_score(path):
path = p_rev
return path
def is_valid_path(n: int, path: List[Coord]) -> bool:
if len(path) != n * n:
return False
used = set(path)
if len(used) != n * n:
return False
for (i, j) in path:
if not (0 <= i < n and 0 <= j < n):
return False
for k in range(n * n - 1):
a, b = path[k], path[k + 1]
if max(abs(a[0] - b[0]), abs(a[1] - b[1])) != 1:
return False
return True
###########################################################
def solve():
path = [(i, j) for i in range(N) for j in range(N)]
mx_score = score(path)
for t in range(8):
tmp_path = two_row_bundle_path(N, t)
tmp_score = score(tmp_path)
if tmp_score > mx_score and is_valid_path(N, tmp_path):
path = tmp_path
mx_score = tmp_score
for r, c in path:
print(r, c)
###########################################################
if __name__ == '__main__':
solve()