## LeetCode Daily Challenge 2024/10/29
#### 2684. Maximum Number of Moves in a Grid
---

### sol1 : using BFS
* This code checks if (i, j) is reachable. If so, it adds the position to the queue. I used depth to monitor the current column, and the maximum depth indicates the maximum number of moves possible (starting from column 0).
* Always create `int[] diri and int[] dirj` to represent the directions for moving on the grid, and use a loop to perform all the movements.
* When dealing with each column, `boolean[] visit` checks if the row has been visited, and is reset to all `false` when moving to the next column.
* `LinkedList<Pair> Q` is a queue dealing with in & out of each node(i, j)
### Code:

import java.util.LinkedList;
class Solution {
    public int maxMoves(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        int[] diri = { 1, 0, -1 };
        int[] dirj = { 1, 1, 1 };
        boolean[] visit = new boolean[m];

        LinkedList<Pair> Q = new LinkedList<>();
        for (int i = 0; i < m; i++) Q.offerLast(new Pair(i, 0));

        int depth = 0;
        while (!Q.isEmpty()) { // BFS
            Pair p = Q.pollFirst();

            if (p.j != depth) {
                depth = p.j;
                visit = new boolean[m];
            }
            for (int k = 0; k < 3; k++) {
                int ii = p.i + diri[k];
                int jj = p.j + dirj[k];

                if (ii < 0 || ii >= m || jj < 0 || jj >= n) continue;
                else if (grid[ii][jj] > grid[p.i][p.j] && !visit[ii]) {
                    visit[ii] = true;
                    Q.offerLast(new Pair(ii, jj));
                }
            }
        }

        return depth;
    }
}

class Pair {
    int i, j;
    Pair (int i, int j) {
        this.i = i;
        this.j = j;
    }
}

---
### sol2 : using dp
>(this problem is more easy if using BFS, while the concept of dp is useful if the problem is `start at any cell`)
* Always create `int[] diri and int[] dirj` to represent the directions for moving on the grid, and use a loop to perform all the movements.
* `dp[i][j]` store the max move **to** (i, j).
* remember that `col[j]` can be updated only after `col[j - 1]` has finished updating.

### Code:

class Solution {
    public int maxMoves(int[][] grid) {
        int[] diri = { -1, 0, 1 }; // up hori down
        int[] dirj = { -1, -1, -1 };

        int[][] dp = new int[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) dp[i][0] = 0;
        
        for (int j = 1; j < grid[0].length; j++) {
            for (int i = 0; i < grid.length; i++) {
                if (i == 0) {
                    int max = 0;
                    for (int k = 1; k < 3; k++) {
                        int ii = i + diri[k];
                        int jj = j + dirj[k];
                        if (grid[i][j] > grid[ii][jj] && !(jj != 0 && dp[ii][jj] == 0)) {
                            max = Math.max(max, dp[ii][jj] + 1);
                        }
                    }
                    dp[i][j] = max;
                } else if (i == grid.length - 1) {
                    int max = 0;
                    for (int k = 0; k < 2; k++) {
                        int ii = i + diri[k];
                        int jj = j + dirj[k];
                        if (grid[i][j] > grid[ii][jj] && !(jj != 0 && dp[ii][jj] == 0)) {
                            max = Math.max(max, dp[ii][jj] + 1);
                        }
                    }
                    dp[i][j] = max;
                } else {
                    int max = 0;
                    for (int k = 0; k < 3; k++) {
                        int ii = i + diri[k];
                        int jj = j + dirj[k];
                        if (grid[i][j] > grid[ii][jj] && !(jj != 0 && dp[ii][jj] == 0)) {
                            max = Math.max(max, dp[ii][jj] + 1);
                        }
                    }
                    dp[i][j] = max;
                }
            }
        }

        int max = 0;
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                max = Math.max(max, dp[i][j]);
            }
        }
        return max;
    }
}