C. Zero Path

Problem - C - Codeforces

额，感觉是很妙妙的题。

首先n+m为偶数那么就不能结果为偶数，即0.而且结果要是能为0，那么所有路上到结果的肯定都是偶数。那么判断可能的最大值和最小值，假如最大值大于0且最小值小于0，那么就说明可能为0的。

因为在所有1，1到n，m的路径里，你拐一个角，就有-2，0，2的综合变换可能。那么，有最小到最大的变换了，一定存在为零的一种状况。

#include <bits/stdc++.h>
using namespace std;
 
#define N 1010
 
int grid[N][N], mn[N][N], mx[N][N];
 
int main() {
    int num_tests;
    cin >> num_tests;
 
    for (int test = 0; test < num_tests; ++test) {
        int n, m;
        cin >> n >> m;
        
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
                cin >> grid[i][j];
        
        mn[0][0] = mx[0][0] = grid[0][0];
        
        for(int i = 1; i < n; ++i)
            mx[i][0] = mn[i][0] = mx[i - 1][0] + grid[i][0];
        
        for(int j = 1; j < m; ++j)
            mx[0][j] = mn[0][j] = mx[0][j - 1] + grid[0][j];
        
        for(int i = 1; i < n; ++i)
            for(int j = 1; j < m; ++j) {
                mx[i][j] = max(mx[i - 1][j], mx[i][j - 1]) + grid[i][j];
                mn[i][j] = min(mn[i - 1][j], mn[i][j - 1]) + grid[i][j];
            }
        
        if(mx[n - 1][m - 1] % 2 || mn[n - 1][m - 1] > 0 || mx[n - 1][m - 1] < 0)
            cout << "NO\n";
        else
            cout << "YES\n";
    }
}