# 2510. Check if There is a Path With Equal Number of 0's And 1's



為什麼需要多一個 count memo? 因為從上面和左邊來的前一個值, 是會不一樣的

equal 0's count and 1's count ->  等於 path sum = -1(0變成-1) + 1 加總合最後是0

O(m\*n\*(m+n)) -> (m+n)是 sum 的可能值, 如果全都 0 -> 這個 count 沿著邊走這個path 會是 m+n (0\~ m+n-1)

````java
```java
class Solution {
    class Step {
        int x;
        int y;
        int sum;
        Step(int x, int y, int sum) {
            this.x = x;
            this.y = y;
            this.sum = sum;
        }
    }
    private static final int[][] DIRS = {{0,1}, {1,0}};
    public boolean isThereAPath(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        //boolean[][][] visited = new boolean[m][n][m+n]; // can't use array, because there is value -1 or -2...
        Set<String> visited = new HashSet<>();
        Queue<Step> queue = new LinkedList<>();
        queue.offer(new Step(0, 0, convertGridValue(grid, 0, 0)));

        while (!queue.isEmpty()) {
            Step cur = queue.poll();
            if (visited.contains(cur.x + "_" + cur.y + "_" + cur.sum)) {
                continue;
            }
            visited.add(cur.x + "_" + cur.y + "_" + cur.sum);
            if (cur.x == m-1 && cur.y == n-1 && cur.sum == 0) {
                return true;
            }

            for (int[] dir : DIRS) {
                int x = cur.x + dir[0];
                int y = cur.y + dir[1];
                if (x < 0 || x >= m || y < 0 || y >= n) {
                    continue;
                }
                queue.offer(new Step(x, y, cur.sum + convertGridValue(grid, x, y)));
            }
        }
        return false;
    }
    private int convertGridValue(int[][] grid, int x, int y) {
        return grid[x][y] == 0 ? -1 : 1;
    }
}
```
````
