检查是否有路径经过相同数量的 0 和 1

2510. 检查是否有路径经过相同数量的 0 和 1

给定一个 下标从 0 开始 的 m x n 的 二进制 矩阵 grid ，从坐标为 (row, col) 的元素可以向右走 (row, col+1) 或向下走 (row+1, col) 。

返回一个布尔值，表示从 (0, 0) 出发是否存在一条路径，经过相同数量的 0 和 1，到达终点 (m-1, n-1) 。如果存在这样的路径返回 true ，否则返回 false 。

示例 1 ：

输入：grid = [[0,1,0,0],[0,1,0,0],[1,0,1,0]]
输出：true
解释：以上图中用蓝色标记的路径是一个有效的路径，因为路径上有 3 个值为 1 的单元格和 3 个值为 0 的单元格。由于存在一个有效的路径，因此返回 true 。

示例 2 ：

输入：grid = [[1,1,0],[0,0,1],[1,0,0]]
输出：false
解释：这个网格中没有一条路径经过相等数量的0和1。

提示：

m == grid.length
n == grid[i].length
2 <= m, n <= 100
grid[i][j] 不是 0 就是 1 。

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: bool isThereAPath(vector<vector<int>>& grid) { } };

java 解法, 执行用时: 32 ms, 内存消耗: 53.5 MB, 提交时间: 2023-10-21 20:22:07

class Solution {
    int[][]dir={{1,0},{0,1}};
    boolean[][][]vis;//记忆化标记
    boolean check=false;
    int m,n;
    public boolean isThereAPath(int[][] grid) {
        this.m=grid.length;
        this.n=grid[0].length;
        this.vis=new boolean[m][n][500];
        if((m+n)%2==0)return false;
        dfs(grid,0,0,0,0);
        return check;
    }
    public void dfs(int[][]grid,int x,int y,int num0,int num1){
        if(x>=m||y>=n)return;
        if(grid[x][y]==0)num0+=1;
        else num1+=1;
        if(x==m-1&&y==n-1){
            if(num0==num1)check=true;
            return;
        }
        if(vis[x][y][250+num0-num1])return ;
        vis[x][y][250+num0-num1]=true;
        for(int []temp:dir)dfs(grid,x+temp[0],y+temp[1],num0,num1);
    }
    
    
    // dp
    public boolean isThereAPath2(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int x = m + n - 1;
        if (x % 2 != 0) return false;
        // dp[i][j][k]表示(0, 0)和(i, j)之间是否存在1的数目减去0的数目等于k-x的路径
        boolean[][][] dp = new boolean[m][n][x * 2 + 1];
        dp[0][0][grid[0][0] == 1 ? x + 1 : x - 1] = true;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < x * 2; k++) {
                    if (grid[i][j] == 1) {
                        if (i > 0 && dp[i - 1][j][k]) dp[i][j][k + 1] = true;
                        if (j > 0 && dp[i][j - 1][k]) dp[i][j][k + 1] = true;
                    } else {
                        if (i > 0 && dp[i - 1][j][k + 1]) dp[i][j][k] = true;
                        if (j > 0 && dp[i][j - 1][k + 1]) dp[i][j][k] = true;
                    }
                }
            }
        }
        return dp[m - 1][n - 1][x];
    }
}

python3 解法, 执行用时: 52 ms, 内存消耗: 17.1 MB, 提交时间: 2023-10-21 20:21:13

class Solution:
    def isThereAPath(self, grid: List[List[int]]) -> bool:
        m, n = len(grid), len(grid[0])
        if (m + n) % 2 == 0:
            return False
        f = [[0] * n for _ in range(m)]
        f[0][0] = 1 << m + n
        for i in range(m):
            for j in range(n):
                if i > 0:
                    f[i][j] |= f[i - 1][j]
                if j > 0:
                    f[i][j] |= f[i][j - 1]
                if grid[i][j] == 1:
                    f[i][j] <<= 1
                else:
                    f[i][j] >>= 1
        return bool(f[-1][-1] & 1 << m + n)
        

    def isThereAPath2(self, grid: List[List[int]]) -> bool:
        m,n = len(grid),len(grid[0])
        # 目标为 m+n-1个格子， 如果它本身都不是偶数，直接返回false
        if (m+n-1)%2 != 0:
            return False 
        # 只能往右边或者下边走
        # dp[i][j][k]表示到i,j格的时候，累计的1有k个
        # i,j本身是1
        # dp[i][j][k] = dp[i][j-1][k-1]|dp[i-1][j][k-1]
        # i,j本身不是1
        # dp[i][j][k] = dp[i][j-1][k]|dp[i-1][j][k]
        dp = [[[False for k in range(m+n+1)] for j in range(n+1)] for i in range(m+1)]
        # base: dp[0][1][0] = True 
        dp[0][1][0] = True 
        for i in range(1,m+1):
            for j in range(1,n+1):
                for k in range(i+j+1): # 这里可以优化成i+j+1
                    if grid[i-1][j-1] == 1:
                        dp[i][j][k] = dp[i][j-1][k-1]|dp[i-1][j][k-1]
                    else:
                        dp[i][j][k] = dp[i][j-1][k]|dp[i-1][j][k]
        return dp[m][n][(m+n-1)//2]

cpp 解法, 执行用时: 8 ms, 内存消耗: 11.1 MB, 提交时间: 2023-10-21 20:20:39

class Solution {
public:
    bool isThereAPath(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        if ((m + n) % 2 == 0) {
            return false;
        }
        vector<vector<bitset<210>>> dp(m + 1, vector<bitset<210>>(n + 1));
        dp[0][1].set(105);
        dp[1][0].set(105);
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (grid[i - 1][j - 1]) {
                    dp[i][j] = (dp[i - 1][j] << 1) | (dp[i][j - 1] << 1);
                } else {
                    dp[i][j] = (dp[i - 1][j] >> 1) | (dp[i][j - 1] >> 1);
                }
            }
        }
        return dp[m][n][105];
    }
};

cpp 解法, 执行用时: 8 ms, 内存消耗: 9.3 MB, 提交时间: 2023-10-21 20:20:22

/***************************************************
Author: hqztrue
https://github.com/hqztrue/LeetCodeSolutions
Complexity: O(nm)
If you find this solution helpful, plz give a star:)
***************************************************/
const int N=105;
int mi[N][N],ma[N][N];
inline void upd_mi(int &x,int y){if (y<x)x=y;}
inline void upd_ma(int &x,int y){if (y>x)x=y;}
class Solution {
public:
	bool isThereAPath(vector<vector<int>>& a) {
		int n=a.size(),m=a[0].size(),t=(n+m-1)/2;
		if ((n+m-1)%2)return 0;
		for (int i=0;i<n;++i)memset(mi[i],0x3f,sizeof(int)*m),memset(ma[i],0,sizeof(int)*m);
		mi[0][0]=ma[0][0]=a[0][0];
		for (int i=0;i<n;++i)
			for (int j=0;j<m;++j){
				int x=a[i][j];
				if (i>=1)upd_mi(mi[i][j],mi[i-1][j]+x),upd_ma(ma[i][j],ma[i-1][j]+x);
				if (j>=1)upd_mi(mi[i][j],mi[i][j-1]+x),upd_ma(ma[i][j],ma[i][j-1]+x);
			}
		return mi[n-1][m-1]<=t&&ma[n-1][m-1]>=t;
	}
};

上一题

下一题

详情