题目背景

小明的学校的礼堂有很多座位, 学生区礼堂开会时, 每次都要有可能有领导入座. 由于领导人数的不一, 老师每次都要给学生重新安排座位. 于是, 老师就让小明设计一个算法, 自动给学校的5个班级安排座位.

题目描述

有一个座位集合$S$: 其中, $S[i][j]=0$代表在$(i,j)$处有一个空座位, $S[i][j]=-1$代表在$(i,j)$处没有座位或没有可用的座位.

S = [
    [-1, -1, -1, -1, -1, -1, -1, -1, -1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
    [-1, -1, -1, -1, -1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
    [-1, -1, -1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
    [-1, -1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
    [-1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
    [-1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
    [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
    [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
    [-1, -1, -1, -1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
    [-1, -1, -1, -1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
    [-1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
    [-1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
    [-1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
    [-1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
    [-1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
    [-1, -1, -1, -1, -1,  0,  0,  0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
]

你可以进行以下操作进行安排座位: 将$S[i][j]=0$调整为为$S[i][j]=c$, 其中$c\in\{1,2,3,4,5\}$.

令 $P_c=\{(i,j)|S[i][j]=c\}$, $A_c=\{i|S[i][j]=c,0\le j\le 7\}$, $B_c=\{i|S[i][j]=c,8\le j\le 18\}$.

你安排的座位需要满足以下条件:

1. $|B_1|=37$, $|B_2|=37$, $|B_3|=35$, $|B_4|=34$, $|B_5|=41$. ($|G|$表示集合$G$的元素总数)
2. 对 $\forall c_1>c_2$, 满足 $A_{c_1min}>A_{c_2max}$ 且 $B_{c_1min}>B_{c_2max}$.
3. 对 $\forall c\in\{1,2,3,4,5\}$, 满足 $A_c\subseteq B_c$ 或 $B_c\subseteq A_c$.

你需要找到一种排座位的方法使得 $\sum\{\sqrt{(i-18)^2+(j+2)^2}|A[i][j]\in\{1,2,3,4,5\}\}$最小.

输出最终的排座位方法 $S$ 即可.