Working around Dynamic Programming
This problem is a classic DP problem, and the hints confirm it. Couldn't solve it using DP, and the brute-force DFS approach was leading to TLE. So... decided to try to work around it.
The heuristic used was simple: if we try way too many interactions (say 10x100x100), then we'll assume that there is no solution. It means that we have tried 10 times more cells that exists on the board. It worked. Sometimes achieving the goals requires creative and shameless approaches. Code is down below, cheers, ACC.
The heuristic used was simple: if we try way too many interactions (say 10x100x100), then we'll assume that there is no solution. It means that we have tried 10 times more cells that exists on the board. It worked. Sometimes achieving the goals requires creative and shameless approaches. Code is down below, cheers, ACC.
2510. Check if There is a Path With Equal Number of 0's And 1's
Medium
You are given a 0-indexed m x n binary matrix grid. You can move from a cell (row, col) to any of the cells (row + 1, col) or (row, col + 1).
Return true if there is a path from (0, 0) to (m - 1, n - 1) that visits an equal number of 0's and 1's. Otherwise return false.
Example 1:
Input: grid = [[0,1,0,0],[0,1,0,0],[1,0,1,0]] Output: true Explanation: The path colored in blue in the above diagram is a valid path because we have 3 cells with a value of 1 and 3 with a value of 0. Since there is a valid path, we return true.
Example 2:
Input: grid = [[1,1,0],[0,0,1],[1,0,0]] Output: false Explanation: There is no path in this grid with an equal number of 0's and 1's.
Constraints:
m == grid.lengthn == grid[i].length2 <= m, n <= 100grid[i][j]is either0or1.
Accepted
206
Submissions
304
public bool IsThereAPath(int[][] grid)
{
int interactions = 0;
return IsThereAPath(grid, 0, 0, 0, 0, ref interactions, 10000000);
}
private bool IsThereAPath(int[][] grid,
int row,
int col,
int numberOnes,
int numberZeroes,
ref int interactions,
int MAX)
{
if (interactions>= MAX) return false;
if (row>= grid.Length || col>= grid[0].Length) return false;
numberOnes = (grid[row][col] == 1) ? numberOnes + 1 : numberOnes;
numberZeroes = (grid[row][col] == 0) ? numberZeroes + 1 : numberZeroes;
if (row == grid.Length - 1 && col == grid[row].Length - 1) return numberOnes == numberZeroes;
int rowsLeft = grid.Length - row - 1;
int colsLeft = grid[0].Length - col - 1;
if (Math.Abs(numberOnes - numberZeroes)> rowsLeft + colsLeft) return false;
interactions++;
if (IsThereAPath(grid, row, col + 1, numberOnes, numberZeroes, ref interactions, MAX)) return true;
interactions++;
return IsThereAPath(grid, row + 1, col, numberOnes, numberZeroes, ref interactions, MAX);
}
Comments
Post a Comment
[γγ¬γΌγ ]