SP23882 DCEPC14H - Watchers On The Wall

John Snow 刚刚被任命为守夜人的指挥官，他的首要任务是再一次抵御野人军队对黑城堡的进攻。 由 Mance Rayder 领导的野人军队是一支凶悍的队伍，包括巨人、塞恩人、角足人、冰河部落和穴居人，每个族群都拥有不同的战斗力。 John 已在该地区修建了多座塔楼。一个塔楼可以向北、西、东、南四个方向中的一个或多个发射炮弹，炮弹会摧毁其路径上的所有敌人，直至遇到墙壁或其他塔楼才会停止。 John 只有一次机会在日出前开火，他希望尽量制造最大的伤害。 你的任务是帮助 John 为每个塔楼确定发射方向（可以是全部、部分甚至不发射），以便使总伤害最大化。但是，任何两条炮弹的路径在没有墙壁或塔楼隔开的情况下不应交叉。 John 也可以选择某些塔楼不进行发射。 所有炮弹同时发射。

第一行输入一个整数 $N$，表示网格的大小。 接下来的 $N$ 行描述了网格的布局，每行包含 $N$ 个字符，字符可以是： - `#`：墙壁 - `T`：塔楼 - `0`：空地 - 数字 $1$ 到 $9$：表示敌人的战斗力

输出一个整数，表示一次射击所能造成的最大伤害。

- $N \leq 500$ - 炮弹数量 $\leq 200$ **本翻译由 AI 自动生成**