解题思路

这是一道典型的二维动态规划 + 极小化极大（minimax）博弈问题。

棋子从左上角 $(1,1)$ 出发，每次只能向右或向下走一步，直到到达右下角 $(n,m)$ 为止。总步数固定为：

题目内容

有一个 $n×m$ 的棋盘，记第 $i$ 行第 $j$ 列为 $a_{i,j}$，其字符仅为 $’0’$ 或，$’1’$。棋盘上有且仅有一个棋子，初始位置在左上角 $(1,1)$。

两名同学轮流操作，同学天才先手。在每一次操作中，当前同学需要将棋子从当前位置向右或向下移动一步(若对应方向越界，则该方向不可选)。移动完成后，若新的格子字符为，$’1’$，则本次移动的同学记 $+1$ 分;若为 $’0’$，则记 $-1$ 分。初始格子 $(1,1)$ 不记分。

当棋子到达右下角 $(n,m)$ 后，游戏立即结束(此时无法继续移动)。请计算在双方都采取最优策略时，天才同学的总分减去笨蛋同学的总分的差值。

输入描述

第一行输入两个整数 $n,m (1≤n,m ≤2×10^5;n×m≤4×10^5)$

此后一共 $n$ 行，每行输入一个长度为 $m$ 的字符串，仅包含字符 $’0’$ 与 $’1’$，表示棋盘。

输出描述

输出一个整数，为最优博弈下天才同学分数减笨蛋同学分数的差值。

样例1

输入

2 2
01
11

输出

0

说明

起点在 $(1,1)$。两条可能的路径如下：

• 先手向右到 $(1,2)$ 记 $+1$ 分，后手向下到 $(2,2)$ 记 $+1$ 分，差值 $+1-(+1)=0$ ;

• 先手向下到 $(2,1)$ 记 $+1$ 分，后手向右到 $(2,2)$ 记 $+1$ 分，差值同样为 $0$ ；

双方最优下差值为 $0$ 。

样例2

输入

1 3
101

输出

-2

视频试看，开通会员即可查看完整视频题解：1.题目讲解 2.思路分析 3.逐行代码手写