Zero Path

Created by LXC on Wed Jul 12 10:34:34 2023

https://codeforces.com/problemset/problem/1695/C

ranting: 1700

tag: brute force, data structures, dp, graphs, greedy, shortest paths

problem

给出一个n*m的二维矩阵，二维矩阵中的元素值只有-1和1。

若当前点为(x,y)只能移动到(x+1,y)或(x,y+1)。

现在求从(0,0)到(n,m)是否存在一条路径其路径和为0。

solution

从(0,0)到(n,m)所经过的格子个数是n+m-1。不妨设这其中有k个-1元素，那么路径总和是n+m-1-2*k，这与n+m-1的奇偶性一致。所以如果n+m-1是个奇数，那么不存在路径和为0。

否则用dp求出从(0,0)到(n,m)的最大路径和mx以及最小路径和mn。

mn与mx均为偶数。可能的路径和是$mn,mn+2,mn+4,\cdots, mx-2, mx$。只要$mn\le 0\le mx$就存在路径和为0的路径。

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n, vector<int>(m, 0)), mn(n, vector<int>(m, 1e9)),
        mx(n, vector<int>(m, -1e9));
    for (auto& i : g) {
        for (auto& j : i)
            cin >> j;
    }
    mx[0][0] = mn[0][0] = g[0][0];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i > 0) {
                mx[i][j] = max(mx[i][j], mx[i - 1][j] + g[i][j]);
                mn[i][j] = min(mn[i][j], mn[i - 1][j] + g[i][j]);
            }
            if (j > 0) {
                mx[i][j] = max(mx[i][j], mx[i][j - 1] + g[i][j]);
                mn[i][j] = min(mn[i][j], mn[i][j - 1] + g[i][j]);
            }
        }
    }
    if (mn[n - 1][m - 1] % 2 || mn[n - 1][m - 1] > 0 || mx[n - 1][m - 1] < 0) {
        cout << "NO\n";
    } else {
        cout << "YES\n";
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}