基准时间限制：1 秒 空间限制：131072 KB
有N行M列的正方形盒子。每个盒子有三种状态0, -1, +1。球从盒子上边或左边进入盒子，从下边或右边离开盒子。规则：
如果盒子的模式是-1，则进入它的球从下面出去。（方向变为向下）
如果盒子的模式是+1，则进入它的球从右面出去。 （反向变为向右）
如果盒子的模式是0， 则进入它的球方向不变。从上面进入的，从下面出去，从左面进入的，从右面出去。
球离开一个盒子，这个盒子的模式切换为相反数。已知，每个盒子的状态，扔k个球，它们都从左上角那个盒子的上面进入（方向向下），问最终有几个球从右下角的盒子的下边出去。
（可以理解维球一个一个放，等待的时间足够长，不会有两个球同时进入一个盒子的情形）本题由Javaman翻译。
Input
第1行：包括3个数M, N, K中间用空格分隔，M,N 为盒子的宽度和高度，K为球的数量(1 <= M, N <= 1000, 1 <= K <= 10^18)。
第2 - N + 1行：每行M个数(-1, 0 或 1)，表示对应的模式。
Output
输出1个数，对应最终有有多少个球从右下角的盒子的下边出去。
Input示例
3 2 4
-1 0 -1
1 0 0
Output示例
1
思路：
考虑到从左上开始方向始终只有右和下，果断dp
可以整体考虑，因为落下一个，就会改变当前的值为相反数，所以一方为n+1/2，一方为n/2
类似考虑，当为+1时，优先考虑对下个右方格子的影响，-1时优先考虑下个左方格子的影响，为0时直接加和
代码：
#include <bits/stdc++.h>
using namespace std;
int dir;
long long dp[][][];
long long read(){
long long res = ;
int flag = ;
char ch;
if ((ch = getchar()) == '-'){
flag = ;
}
else if(ch >= '' && ch <= ''){
res = ch - '';
}
while ((ch = getchar()) >= '' && ch <= ''){
res = res * + (ch - '');
}
return flag ? -res : res;
}
int main() {
int n,m;
long long k;
m=read();n=read();k=read();
//用0来表示-1朝下，1来表示+1朝右
//刚开初始放下为朝下，全部球落入dp[1][1][0],dp[1][1][1]=0;
dp[][][]=k;
for(int i=;i<=n;++i) {
for(int j=;j<=m;++j) {
//不同再开数组保存方向，因为一行一行处理没有后效性
dir=read();
long long sum=dp[i][j][]+dp[i][j][];//当前关口的总数
if(dir==) {
dp[i][j+][]+=dp[i][j][];//朝右j+1
dp[i+][j][]+=dp[i][j][];//朝下i+1
} else if(dir==-) {
dp[i+][j][]+=(sum+)>>;//先计算朝下的,i+1，状态0
dp[i][j+][]+=sum>>;//剩余的朝右j+1,状态1
} else if(dir==) {
dp[i][j+][]+=(sum+)>>;//先计算朝右的,j+1，状态1
dp[i+][j][]+=sum>>;//剩余的朝右i+1,状态0
}
}
}
printf("%lld\n",dp[n+][m][]);//由dp[n][m][0]->dp[n+1][m][0]
return ;
}