枚举所有可能的方向 (dx,dy,dz)。
其中 dx,dy,dz∈−1,0,1,且不能同时为 0,一共有 26 个方向。
对于某个方向:
如果某一维的步长为 1,起点这一维只能是 0;
给出一个边长为 n 的立方体网格。网格中每个小方块对应一个整数权值。你需要从立方体中选择一条长度为 n 的直线。
允许选择的直线方向包括:沿坐标轴方向(分别与 x、y 或 z 轴平行的整行/整列/整柱);沿任一坐标平面的面对角线方向(例如在 xOy 平面中,每一步 x 与 y 同时加 ±1、z 不变;其余两个平面同理);沿空间对角线方向(每一步 x、y、z 同时加 ±1)。
形式化地,设方向步长为 (dx,dy,dz),其中 dx,dy,dz∈{−1,0,1} 且不全为 0。选择方向后,起点 (x0,y0,z0) 需要满足:对所有 k=0,1,…,n−1,都有 0≤x0+kdx,y0+kdy,z0+kdz≤n−1,从而得到一条恰好经过 n 个小方块的直线。请计算在所有允许方向与所有合法起点中,经过的小方块权值之和的最大值。
在一行上输入一个整数 n(1≤n≤100),表示立方体的边长。
此后 n×n 行,按“层”的顺序给出权值。对于第 k 个“层”,输入 n 行:第 i 行输入 n 个整数 ai,0,k,ai,1,k,…,ai,n−1,k(−106≤ai,j,k≤106),表示第 k 层第 i 行第 j 列小方块的权值。共计输入 n×n×n 个整数。
输出一个整数,表示所有允许方向与所有合法起点中,经过的小方块权值之和的最大值。
输入
2
1 2
3 4
5 6
7 8
输出
15
说明
立方体边长 n=2。第 0 层 a⋅,⋅,0 的两行为 1,2 和 3,4;第 1 层 a⋅,⋅,1 的两行为 5,6 和 7,8。
枚举所有方向所有合法起点,几条候选直线权值和:沿 x 方向 (0,1,1)→(1,1,1) 为 6+8=14;沿 y 方向 (1,0,1)→(1,1,1) 为 7+8=15;沿 z 方向 (1,1,0)→(1,1,1) 为 4+8=12;沿 xy 面对角 (0,0,1)→(1,1,1) 为 5+8=13;沿空间对角 (0,0,0)→(1,1,1) 为 1+8=9。最大值为 15。