题目内容

在一个 $n \times m$ 的网格上，每个格子内写有字符 0 或 1。 游戏开始时，一枚令牌位于左上角 $(1,1)$。玩家 Alice 和 Bob 轮流移动令牌，Alice 先手。每次移动只能选择向右或向下移动一格（不能越界）。 当令牌进入一个新格子时，根据格子内容为当前移动者带来得分或扣分：如果是 1，该玩家获得 $+1$ 分；如果是 0，该玩家获得 $-1$ 分。起始格 $(1,1)$ 不计分。 令牌一旦到达右下角 $(n,m)$，游戏立即结束（无法继续移动）。 双方都采取最优策略，即 Alice 希望最大化（Alice 总分 - Bob 总分）的差值，Bob 希望最小化该差值。请计算最终 Alice 的总分减去 Bob 的总分的差值。

约束条件：

• 行数 $n$ 和列数 $m$ 满足 $1 \le n, m \le 2 \times 10^5$，且 $n \times m \le 4 \times 10^5$。
• 网格中的每个字符仅为 0 或 1。

输入描述

第一行包含两个整数 $n$ 和 $m$，以空格分隔。 接下来的 $n$ 行，每行包含一个长度为 $m$ 的字符串，由字符 0 和 1 组成，依次表示该行的格子内容。

输出描述

输出一个整数，表示在双方最优策略下 Alice 总分减去 Bob 总分的差值。

样例1

输入

1 1
1

输出

0

说明

网格大小为 $1 \times 1$，起点和终点都是 $(1,1)$。游戏开始时令牌已在终点，无法移动，也没有任何得分。因此 Alice 总分与 Bob 总分均为 0，差值 $0 - 0 = 0$。

样例2

输入

1 2
01

输出

1

说明

网格只有一行两列。令牌初始在 $(1,1)$，Alice 先手，只能向右移动到 $(1,2)$。 $(1,2)$ 的字符为 1，Alice 获得 $+1$ 分。到达右下角后游戏结束，Bob 没有操作机会，得分为 0。 最终差值 $1 - 0 = 1$。

样例3

输入

2 1
1
0

输出

-1

说明

网格只有两行一列。令牌初始在 $(1,1)$，Alice 先手，只能向下移动到 $(2,1)$。 $(2,1)$ 的字符为 0，Alice 获得 $-1$ 分，游戏立即结束。Bob 未移动，得分为 0。 最终差值 $(-1) - 0 = -1$。

样例4

输入

2 2
10
10

输出

2

说明

网格为 $2 \times 2$：第一行 10，第二行 10。令牌初始在 $(1,1)$，该格子字符 1 不计分。 Alice 先手，有两种选择：

• 向右移动到 $(1,2)$（字符 0），Alice 得 $-1$ 分。之后 Bob 在 $(1,2)$ 只能向下移动到 $(2,2)$（字符 0），Bob 得 $-1$ 分，差值 $(-1) - (-1) = 0$。
• 向下移动到 $(2,1)$（字符 1），Alice 得 $+1$ 分。之后 Bob 在 $(2,1)$ 只能向右移动到 $(2,2)$（字符 0），Bob 得 $-1$ 分，差值 $(+1) - (-1) = 2$。 双方均采取最优策略，Alice 会选择向下，得到最大差值 2。

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