题目分析

给定一个$n \times m$的网格，其中每个位置可能是可通行的空方格（0）或是地雷方格（1）。我们需要找到有多少个地雷方格能够消灭影子怪兽。我们从网格的中点出发，怪兽从网格中点的右下方出发。每次你移动一步，怪兽会做相反的动作，目标是通过踩到地雷方格来消灭怪兽。与此同时，你必须保证自己的移动不进入地雷方格。

思路

1. 模拟移动过程

我们可以通过模拟网格中的移动过程来解这个问题。关键的思想是你和怪兽总是做相反的移动，因此你可以通过遍历你的每一次可能的合法移动来判断怪兽是否会被消灭。

题目内容

给定一个$n$行$m$ 列的网格，且保证$n,m$都为偶数。我们用$(i,j)$表示第$i$行第$j$列的单元格。

每个单元格要么是可通行的空方格$0$，要么是不可通行的地雷方格$1$。

网格的四周都是墙，你可以在空方格上上下左右移动:

• 从$(x,y)$向上移动到$(x- 1,y)$;

• 向下移动到$(x+1,y)$;

• 向左移动到$(x,y-1)$;

• 向右移动到$(x,y+1)$。

你初始位于$(\frac{n}{2},\frac{m}{2})$，影子怪兽初始位于$(\frac{n}{2}+1,\frac{m}{2}+1)$

每当你移动一次，怪兽就朝相反方向移动一次，直到怪兽被消灭。

由于它始终和你做相反移动，无法被你直接追上。

不过，网格中有地雷方格可以消灭它。

请计算有多少不同的地雷方格可以消灭影子怪兽。你需要保证自己始终不会踏入地雷方格。

输入描述

第一行输入两个整数$n,m(4 ≤n×m≤10^6)$,表示网格大小。题目保证$n,m$都为偶数。

接下来$n$行，每行输入$m$个整数$a_{i,j}∈${$0,1$}，表示网格:

• $0$表示空方格;

• $1$表示地雷方格。

同时保证你和影子怪兽的初始位置所在单元格均为$0$

输出描述

输出一个整数，表示可以用来消灭影子怪兽的地雷方格总数。

样例1

输入

4 2
1 0
0 0 
1 0
1 1

输出

1

说明

• 你可以向右移动一格此时怪兽向左移动一格到达地雷被消灭，而你无法向上移动因为你上方是一个地雷方格。

样例2

输入

2 2
0 0 
0 0

输出

0

说明

• 此时网格中无地雷方格。
• 无法消灭怪兽,答案为$0$。