口是心非的雞塊同學
發布時間: Feb. 8, 2021, 12:11 a.m. 最後更新時間: Sept. 14, 2023, 10:58 p.m. 時間限制: 1000ms 記憶體限制: 128M
眾所皆知的，雞塊是個現充，具體說他有多現充的話，大概就是開學超過三個月，班上有加臉書好友的人卻還只有6個
除此之外，認識的(可能是女生的)女生有超過$\frac{2}{3}$都沒看過本人，只看過她們在VTB宇宙的造型。這樣的他還是個大胃王，每個月開銷第二大來源是飯錢(順帶一提，第一是每天放學後在音遊店繳的稅金，而第三大則是每個月奉獻給背後實際上是大叔的VTBer的善款)，這樣的雞塊簡直就是把現充和現充混在一起大火快炒，再淋上一大勺現充調味露提味的超級現充！
然而，這樣現(ㄈㄟˊ)充(ㄓㄞˊ)的他想做出改變！具體來說就是想交上一些會幫他繳稅的(X)朋友！但你也知道，對於一個口是心非的臭肥宅而言，交上朋友是那麼的困難。於是他就跑去學校附近的神社砸錢，對，人生卡關砸錢就會過了！總之因為他砸了太多錢，在這個神明都看業績的時代他於是受到了神明的特別關照，作為其結果，他獲得了一個能力：走到一個地方，則那個地方的所有人都會變成他的朋友(但取而代之的，他們不會幫雞塊繳稅)
在得知自己取得的能力之後，雞塊決定在下個學期初在班上「出巡」。假設他的班上座位可以被表示成一張$N\times N(1\leq N\leq 9)$的地圖，在早修的班上，你也知道不會有人乖乖待在自己的位子上(除了昨天晚上因為肝油戲打太晚需要睡覺+沒朋友的雞塊同學)，所以會有一些人跑到別人的位子，加上雞塊的班上有一些和雞塊格格不入的真·現充，所以會有很多別班的人跑來。然而雞塊有社交恐懼症，所以雞塊決定從他的位子，也就是教室左上角的$(1,1)$走到教室右下角的$(N,N)$，再從$(N,N)$走回$(1,1)$。
注意一開始雞塊只能往右邊或往下走，走回來的時候只能往左邊或上面走，且被他走過的地方上的所有人都會變成雞塊的朋友，加上因為他沒有賢者之石，所以每個人最多只能和他成為一次朋友。想請教你雞塊在走過去走回來之後最多能交到幾個朋友？
也就是說，給你一張$N\times N$的帶權矩陣，問你從$(1,1)$走到$(N,N)$+再從$(N,N)$走回$(1,1)$的最大權值，其中每個權值最多可以被拿一次
第一行有一個整數$N(1\leq N\leq 9)$，表示座位有幾行/列，接下來有$N$行輸入
接下來每行有$N$個整數，每個整數表示該座位上聚集的人數
輸出一行一個整數表示雞塊在走完之後最多可以交到幾個朋友，保證答案不超出int範圍
8 0 0 0 0 0 0 0 0 0 0 13 0 0 6 0 0 0 0 0 0 7 0 0 0 0 0 0 14 0 0 0 0 0 21 0 0 0 4 0 0 0 0 15 0 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0
67
4 9 0 0 3 0 9 0 2 0 0 1 0 0 2 0 0
25
