Join Us
Loading Similar Posts
Entering edit mode
from collections import deque
dx = [1, 1, -1, -1]
dy = [-1, 1, 1, -1]
def read_input():
n = int(input())
vec = [list(map(int, input().split())) for _ in range(n)]
return n, vec
def is_valid(nx, ny, ind, n, vis):
return ind <= nx <= n - ind - 1 and ind <= ny <= n - ind - 1 and not vis[nx][ny]
def bfs_diamond(n, vec, ind, j, vis):
temp = []
cnt = 0
q = deque([(j, n // 2)])
tempsum = 0
while q:
x, y = q.popleft()
vis[x][y] = True
tempsum += vec[x][y]
temp.append(vec[x][y])
nx, ny = x + dx[cnt], y + dy[cnt]
if is_valid(nx, ny, ind, n, vis):
vis[nx][ny] = True
q.append((nx, ny))
else:
cnt += 1
if cnt == 4:
break
nx, ny = x + dx[cnt], y + dy[cnt]
q.append((nx, ny))
return temp, tempsum
def find_max_diamond(n, vec):
ind = 0
mx_ind = -1
mx_sum = 0
vis = [[False] * (n+1) for _ in range(n+1)]
diamonds = []
for j in range(n // 2):
temp, tempsum = bfs_diamond(n, vec, ind, j, vis)
diamonds.append(temp)
if tempsum > mx_sum:
mx_sum = tempsum
mx_ind = ind
ind += 1
return diamonds, mx_ind, mx_sum
def construct_final_answer(diamonds, mx_ind):
final_ans = [diamonds[mx_ind][0]]
i, j = 1, len(diamonds[mx_ind]) - 1
while i <= j:
if i == j:
final_ans.append(diamonds[mx_ind][i])
i += 1
else:
final_ans.append(diamonds[mx_ind][i])
final_ans.append(diamonds[mx_ind][j])
i += 1
j -= 1
return final_ans
def main():
n, vec = read_input()
diamonds, mx_ind, mx_sum = find_max_diamond(n, vec)
final_ans = construct_final_answer(diamonds, mx_ind)
print(" ".join(map(str, final_ans)))
print(mx_sum)
if __name__ == "__main__":
main()
