解题思路

操作效果：选择第 $i$ 行和第 $j$ 列后，这两条线上的 'Z' 都会变成 'N'。交点 $(i,j)$ 只应被计算一次。
增量公式：设初始 'N' 的个数为 $\textit{init}$ ，第 $i$ 行的 'Z' 个数为 $r_i$ ，第 $j$ 列的 'Z' 个数为 $c_j$ 。选择 $(i,j)$ 后新增的 'N' 个数为 $\Delta(i,j)=r_i+c_j-[grid[i][j]=\texttt{Z}].$
枚举最优十字：预处理每行、每列的 'Z' 计数后，枚举所有行列表，取最大 $\Delta$ ，答案为 $\textit{init}+\Delta_{\max}$ 。

复杂度分析

给定一个 $n$ 行 $m$ 列的网格，每个格子上写着大写字母 'N' 或 'Z'。

你可以恰好选择一整行和一整列，把这条十字区域内所有的 'Z' 改写成 'N'。请输出操作后网格中 'N' 的最大可能数量。

行数 $n$ 与列数 $m$ 满足 $1 \le n,m \le 10^3$ 。

第一行包含两个正整数 $n$ 和 $m$ ，表示网格的行数和列数。接下来 $n$ 行，每行一个长度为 $m$ 的字符串，仅由大写字母 'N' 和 'Z' 组成，表示该行的格子。