thảo luận Leetcode mỗi ngày

function maxMoves(grid: number[][]): number {
    const m = grid.length, n = grid[0].length;
    const dp = Array.from({ length: m }, () => Array(n).fill(0));
    let res = 0;
    for (let i = 0; i < m; i++) {
        dp[i][0] = 1;
    }
    for (let j = 1; j < n; j++) {
        for (let i = 0; i < m; i++) {
            let cur = 0;
            if (i > 0 && grid[i - 1][j - 1] < grid[i][j] && dp[i-1][j-1]) {
                cur = Math.max(cur, dp[i - 1][j - 1] + 1);
            }
            if (grid[i][j - 1] < grid[i][j] && dp[i][j-1]) {
                cur = Math.max(cur, dp[i][j - 1] + 1);
            }
            if (i < m - 1 && grid[i + 1][j - 1] < grid[i][j] && dp[i + 1][j-1]) {
                cur = Math.max(cur, dp[i + 1][j - 1] + 1);
            }
            
            dp[i][j] = cur;
            res = Math.max(res, cur - 1);
        }
    }
    return res;
}

var maxMoves = function(grid) {
    const m = grid.length, n = grid[0].length;
    let [prev, now] = Array(2).fill().map(() => Array(m).fill(false));
    let ans = 0;
    now.fill(true);
    for (let col = 1; col < n; col++) {
        [now, prev] = [prev, now];
        now.fill(false);
        for (let i = 0; i < m; i++) {
            for (let j = i - 1; j <= i + 1; j++) {
                if (j >= 0 && j < m && prev[j] && grid[j][col-1] < grid[i][col]) {
                    now[i] = true;
                }
            }
        }
        if (!now.includes(true)) {
            return col - 1;
        }
    }
    return n - 1;
};

class Solution {
public:
    int maxMoves(vector<vector<int>>& grid) {
        const int m = grid.size();
        const int n = grid[0].size();
        queue<int> q;
        set<int> st;
        for (int row = 0; row < m; ++row)
            q.push(row * n);
        int move = -1;
        int cell, row, col;
        size_t qsize, i;
        while (!q.empty()) {
            move++;
            qsize = q.size();
            for (i = 0; i < qsize; ++i) {
                cell = q.front(); q.pop();
                row = cell / n;
                col = cell % n;
                if (col == n - 1)
                    continue;
                if (grid[row][col] < grid[row][col + 1])
                    st.insert(cell + 1);
                if (row > 0 && grid[row][col] < grid[row - 1][col + 1]) {
                    st.insert(cell - n + 1);
                }
                if (row < m - 1 && grid[row][col] < grid[row + 1][col + 1]) {
                    st.insert(cell + n + 1);
                }
            }
            while (!st.empty()) {
                q.push(*st.begin());
                st.erase(st.begin());
            }
        }
        return move;
    }
};

class Solution {
    public int maxMoves(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] matrix = new int[n][m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                matrix[j][i] = grid[i][j];
            }
        }
        int row = matrix.length;
        int col = matrix[0].length;
        int[][] dp = new int[row][col];
        int max = 0;
        for (int i = 0; i < col; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < row; i++) {
            for (int j = 0; j < col; j++) {
                for (int k = -1; k <= 1; k++) {
                    if (j + k >= 0 && j + k <= col - 1) {
                        if (matrix[i][j] > matrix[i - 1][j + k] && dp[i - 1][j + k] > 0) {
                            dp[i][j] = Math.max(dp[i][j], dp[i - 1][j + k] + 1);
                        }
                    }
                    max = Math.max(max, dp[i][j] - 1);
                }
            }
        }
        return max;
    }
}

class Solution {

    public int maxMoves(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        int ans = 0;
        int[][] dp = new int[row][col];
        for (int i = 0; i < row; i++) {
            ans = Math.max(ans, dfs(grid, dp, i, 0));
        }
        return ans - 1;
    }

    private int dfs(int[][] grid, int[][] dp, int row, int col) {
        if (col == grid[0].length - 1) return 1;
        if (dp[row][col] != 0) return dp[row][col];

        int maxMoves = 0;
        int current = grid[row][col];
        if (row - 1 >= 0 && col + 1 < grid[0].length && current < grid[row - 1][col + 1]) {
            maxMoves = Math.max(maxMoves, dfs(grid, dp, row - 1, col + 1));
        }
        if (col + 1 < grid[0].length && current < grid[row][col + 1]) {
            maxMoves = Math.max(maxMoves, dfs(grid, dp, row, col + 1));
        }
        if (row + 1 < grid.length && col + 1 < grid[0].length && current < grid[row + 1][col + 1]) {
            maxMoves = Math.max(maxMoves, dfs(grid, dp, row + 1, col + 1));
        }
        dp[row][col] = maxMoves + 1;
        return dp[row][col];
    }

}

class Solution:
    def maxMoves(self, grid: List[List[int]]) -> int:
        queue = deque()
        m, n = len(grid), len(grid[0])
        directions = [(-1, 1), (0, 1), (1, 1)]
        moves = 0
        visited = set()

        for i in range(m):
            queue.append((i, 0)) # i, j
            visited.add((i, 0))

        while queue:
            lenQ = len(queue)
            for _ in range(lenQ):
                i, j = queue.popleft()

                for d in directions:
                    newI, newJ = i + d[0], j + d[1]
                    if 0 <= newI < m and 0 <= newJ < n and grid[i][j] < grid[newI][newJ] and (newI, newJ) not in visited:
                        queue.append((newI, newJ))
                        visited.add((newI, newJ))
            moves += 1
            
        return  moves - 1

class Solution {
    int max = 0;
    public int maxMoves(int[][] grid) {
        int r = grid.length;
        int c = grid[0].length;
        boolean[][] visited = new boolean[r][c];
        int index = 0;
        for(int i = 0;i<r;i++)
            for(int j = 0;j<3;j++)
                dfs(i,0,i-1+j,1,0,grid,visited);
      
        return max;
    }

    public void dfs(int r1,int c1, int r,int c, int times, int[][] grid, boolean[][] visited){
        if(
            r<0||
            r>=grid.length||
            c>=grid[0].length||
            grid[r][c]<=grid[r1][c1]
        ){
            max = Math.max(max,times);
            return;
        }

        if(visited[r][c])
            return;
      
      
        for(int j = 0;j<3;j++)
            dfs(r,c,r-1+j,c+1,times+1,grid,visited);
        visited[r][c] = true;
      
    }
}