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

class Solution:
    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
        ans = 0
        maxMove -= 1
        if m == 1 and n == 1:
            return 4
        def calculateWays(row, column):
            nonlocal ans
            if (row == 0 and column == 0) or (row == 0 and column == n - 1) or (row == m - 1 and column == 0) or (row == m - 1 and column == n - 1):
                if m == 1 or n == 1:
                    ans += 3
                else:
                    ans +=2

            elif row == 0 or row == m - 1 or column == 0 or column == n-1:
                if m == 1 or n == 1:
                    ans += 2
                else:
                    ans +=1
    
        queue = deque()
        queue.append((startRow, startColumn, 0))
        while queue:
            row, column, moves = queue.popleft()
            if moves <= maxMove:
                calculateWays(row, column)
                neighbors = []
                neighbors.append((row - 1, column))
                neighbors.append((row + 1, column))
                neighbors.append((row, column - 1))
                neighbors.append((row, column + 1))
                for neighbor in neighbors:
                    nextRow, nextColumn = neighbor
                    if nextRow < 0 or nextColumn < 0 or nextRow == m or nextColumn == n:
                        continue

                    queue.append((nextRow, nextColumn, moves + 1))

        return ans%(10**9 + 7)

class Solution:
    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
        ans = 0
        # Just one row one column
        if m == 1 and n == 1:
            return 4
        def getNumways(row, column):
            # If we are at the 4 corners of grid
            if (row == 0 and column == 0) or (row == 0 and column == n - 1) or (row == m - 1 and column == 0) or (row == m - 1 and column == n - 1):
                # Return 3 ways if m or n == 1
                if m == 1 or n == 1:
                    return 3
                # Return 2 ways if m and n > 1
                else:
                    return 2

            # If we are at the boundaries
            elif row == 0 or row == m - 1 or column == 0 or column == n-1:
                # Return 2 ways (top and down, left and right) if m or n == 1
                if m == 1 or n == 1:
                    return 2
                # Return 1 ways (top or down, left or right) if m or n == 1
                else:
                    return 1
            return 0
     
        @lru_cache(None)
        def dp(row, column, moves):
            if row < 0 or column < 0 or row == m or column == n or moves == 0:
                return 0
 
            ans = getNumways(row, column)
            ans += dp(row, column - 1, moves - 1)
            ans += dp(row, column + 1, moves - 1)
            ans += dp(row - 1, column, moves - 1)
            ans += dp(row + 1, column, moves - 1)
            return ans
        return dp(startRow, startColumn, maxMove)%(10**9 + 7)

class Solution:
    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
        ans = 0
      
        @lru_cache(None)
        def dp(row, column, moves):
            if moves < 0:
                return 0

            if row < 0 or column < 0 or row == m or column == n:
                return 1

            ans = 0
            ans += dp(row, column - 1, moves - 1)
            ans += dp(row, column + 1, moves - 1)
            ans += dp(row - 1, column, moves - 1)
            ans += dp(row + 1, column, moves - 1)
            return ans

        return dp(startRow, startColumn, maxMove)%(10**9 + 7)

function findPaths(m: number, n: number, maxMove: number, startRow: number, startColumn: number): number {
    const mod = 1e9 + 7;
    const dirs = [[0,1], [1,0], [0, -1], [-1,0]];
    const memo = Array.from({ length: m }, () => Array.from({ length: n }, () => new Array(maxMove + 1).fill(-1)));

    const go = (r: number, c: number, move: number) => {
        if (r < 0 || r === m || c < 0 || c === n) return 1;
        if (memo[r][c][move] !== -1) return memo[r][c][move];
        if (move === 0) return 0;
        let res = 0;
        for (const [x, y] of dirs) {
            res = (res + go(r + x, c + y, move - 1)) % mod;
        }
        memo[r][c][move] = res;
        return memo[r][c][move];
    }
    return go(startRow, startColumn, maxMove);
};

public class Solution {
    const int MOD = 1_000_000_007;

    public int FindPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        int?[,,] memo = new int?[m,n,maxMove+1];

        int solve(int row, int col, int remainingMove)
        {
            if (remainingMove < 0)
                return 0;
            if (row < 0 || col < 0 || row >= m || col >= n)
            {
                return 1;
            }
            if (memo[row, col, remainingMove] != null)
                return memo[row, col, remainingMove].Value;
            
            memo[row, col, remainingMove] = 0;
            memo[row, col, remainingMove] = (memo[row, col, remainingMove] +  solve(row-1,col,remainingMove-1)) % MOD;
            memo[row, col, remainingMove] = (memo[row, col, remainingMove] +  solve(row+1,col,remainingMove-1)) % MOD;
            memo[row, col, remainingMove] = (memo[row, col, remainingMove] +  solve(row,col-1,remainingMove-1)) % MOD;
            memo[row, col, remainingMove] = (memo[row, col, remainingMove] +  solve(row,col+1,remainingMove-1)) % MOD;
            return memo[row, col, remainingMove].Value;
        }

        var ret = solve(startRow, startColumn, maxMove);
        //log();
        return ret;


        void log()
        {
            for (var move = 0; move <= maxMove; move++)
            {
                Console.WriteLine($"move {move}");
                for (var r = 0; r < m; r++)
                {
                    for (var c = 0; c < n; c++)
                    {
                        Console.Write($"{memo[r,c,move]},");
                    }
                    Console.WriteLine();
                }
            }
        }
    }
}

class Solution:
    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
        @cache
        def dfs(x, y, move):
            if x < 0 or y < 0 or x == m or y == n:
                return 1
            if move == 0:
                return 0
            return sum(dfs(x + i, y + j, move - 1) for i, j in [(1,0), (-1, 0), (0, 1), (0,-1)])%int(1e9 + 7)
        return dfs(startRow, startColumn, maxMove)

public class Solution {
    int e = 1000000007;
    public int FindPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        int[,,] dp = new int[m, n, maxMove + 1];
        for(int i = 0;i<m;i++)
            for(int j = 0;j<n;j++)
                for(int k = 0;k<=maxMove;k++)
                    dp[i, j, k] = -1;
        return move(m, n, maxMove, startRow, startColumn, dp);
    }

    int move(int m, int n, int maxMove, int startRow, int startColumn, int[,,] dp) {
        if(isOutOfBoundary(m, n, startRow, startColumn))
            return 1;
        if(maxMove <= 0)
            return 0;
        if(dp[startRow, startColumn, maxMove] != -1)
            return dp[startRow, startColumn, maxMove];

        long count = 0;
        count += move(m, n, maxMove - 1, startRow - 1, startColumn, dp);
        count += move(m, n, maxMove - 1, startRow + 1, startColumn, dp);
        count += move(m, n, maxMove - 1, startRow, startColumn - 1, dp);
        count += move(m, n, maxMove - 1, startRow, startColumn + 1, dp);

        return dp[startRow, startColumn, maxMove] = (int)(count % e);
    }

    public bool isOutOfBoundary(int m, int n, int row, int col) {
        return row < 0 || row >= m || col < 0 || col >= n;
    }
}

public class Solution {
    int e = 1000000007;
    public int FindPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        if(maxMove == 0) return 0;
        int[,,] dp = new int[m + 2, n + 2, maxMove];

        for(int i = 1;i<=m;i++) {
            dp[i, 1, 0]++;
        }

        for(int i = 1;i<=m;i++) {
            dp[i, n, 0]++;
        }

        for(int i = 1;i<=n;i++) {
            dp[1, i, 0]++;
        }

        for(int i = 1;i<=n;i++) {
            dp[m, i, 0]++;
        }

        for(int k = 1;k<maxMove;k++) {
            for(int i = 1;i<=m;i++) {
                for(int j = 1;j<=n;j++) {
                    long sum = 0;
                    sum += dp[i - 1, j, k-1];
                    sum += dp[i + 1, j, k-1];
                    sum += dp[i, j - 1, k-1];
                    sum += dp[i, j + 1, k-1];
                    dp[i, j, k] = (int)(sum % e);
                }
            }
        }

        long res = 0;
        for(int k = 0;k<maxMove;k++) {
            res+=dp[startRow+1, startColumn + 1, k];
            res%=e;
        }
        return (int)res;
    }
}

var findPaths = function(m, n, maxMove, startRow, startColumn) {
    const MOD = 1e9 + 7;
    const moves = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    const memo = {};
    const go = (i, j, k) => memo[i * 51 * 51 + j * 51 + k] ??= (() => {
        if (i < 0 || i >= m || j < 0 || j >= n) {
            return 1;
        }
        if (!k) {
            return 0;
        }
        let res = 0;
        for (const [ii, jj] of moves) {
            res += go(i + ii, j + jj, k - 1);
        }
        return res % MOD ;
    })();
    return go(startRow, startColumn, maxMove);
};

class Solution {
    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        Map<List<Integer>, Integer> matrix = new HashMap<>();
        List<Integer> startPoint = List.of(startRow, startColumn);
        int result = 0;
        int MOD = 1000000007;
        matrix.put(startPoint, 1);

        while (maxMove > 0) {
            Map<List<Integer>, Integer> newMatrix = new HashMap<>();
            for (Map.Entry<List<Integer>, Integer> entry : matrix.entrySet()) {
                List<Integer> point = entry.getKey();
                int ways = entry.getValue();
                result = (result + move(point, matrix, newMatrix, m, n)) % MOD;
            }
            matrix = newMatrix;
            maxMove--;
        }

        return result;
    }

    private int move(List<Integer> point, Map<List<Integer>, Integer> matrix, Map<List<Integer>, Integer> newMatrix, int m, int n) {
        int result = 0;
        int x = point.get(0);
        int y = point.get(1);

        int ways = matrix.get(point);

        List<List<Integer>> movements = List.of(List.of(x + 1, y), List.of(x - 1, y), List.of(x, y + 1), List.of(x, y - 1));

        for(List<Integer> movement: movements) {
            int ver = movement.get(0);
            int hor = movement.get(1);

            if (ver < 0 || ver >= m || hor < 0 || hor >= n) {
                result = (result + ways) % 1000000007;
            } else {
                newMatrix.put(movement, (newMatrix.getOrDefault(movement, 0) + ways) % 1000000007);
            }
        }

        return result;
    }
}

class Solution {
    static final double mod = (1e9 + 7);
    public static int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        int[][][] dp = new int[m][n][maxMove + 1];
        for (int[][] matrix : dp) {
            for (int[] arr : matrix) {
                Arrays.fill(arr, -1);
            }
        }
        return dfs(m, n, maxMove, startRow, startColumn, dp);
    }

    private static int dfs(int row, int col, int move, int x, int y, int[][][] dp) {
        if (x < 0 || x == row || y < 0 || y == col) {
            return 1;
        }
        if (move == 0) {
            return 0;
        }
        if (dp[x][y][move] >= 0) {
            return dp[x][y][move];
        }
        dp[x][y][move] = (int) ((dfs(row, col, move - 1, x + 1, y, dp)  % mod +
                dfs(row, col, move - 1, x - 1, y, dp) % mod +
                dfs(row, col, move - 1, x, y + 1, dp) % mod +
                dfs(row, col, move - 1, x, y - 1, dp) % mod) % mod);
        return (int) (dp[x][y][move] % mod);
    }
}

public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
    int[][][] map = new int[m + 2][n + 2][maxMove + 1];
    int mod = 1_000_000_007;
    if (maxMove == 0)
        return 0;
    for (int r = 1; r <= m; r++) {
        map[r][1][1]++;
        map[r][n][1]++;
    }

    for (int j = 1; j <= n; j++) {
        map[1][j][1]++;
        map[m][j][1]++;
    }

    for (int move = 2; move <= maxMove; move++) {
        for (int r = 1; r <= m; r++) {
            for (int c = 1; c <= n; c++) {
                map[r][c][move] = (map[r - 1][c][move - 1] % mod + map[r + 1][c][move - 1] % mod)%mod + (map[r][c - 1][move - 1] % mod + map[r][c + 1][move - 1] % mod) % mod;
            }
        }
    }

    int result = 0;
    for (int i = 1; i <= maxMove; i++)
        result = result % mod + map[startRow + 1][startColumn + 1][i] % mod;
    return result % mod;
}

public class Solution
{
    public int FindPaths(int m, int n, int maxMove, int startRow, int startColumn)
    {
        const int MOD = 1000000007;
        int[][][] dp = new int[m][][];
      
        for (int i = 0; i < m; i++)
        {
            dp[i] = new int[n][];
            for (int j = 0; j < n; j++)
            {
                dp[i][j] = new int[maxMove + 1];
            }
        }
      
        int[][] directions = new int[][] { new int[] {0, 1}, new int[] {1, 0}, new int[] {0, -1}, new int[] {-1, 0} };
      
        for (int k = 1; k <= maxMove; k++)
        {
            for (int i = 0; i < m; i++)
           {
                for (int j = 0; j < n; j++)
                {
                    foreach (var dir in directions)
                    {
                        int ni = i + dir[0];
                        int nj = j + dir[1];
                      
                        if (ni >= 0 && ni < m && nj >= 0 && nj < n)
                        {
                            dp[i][j][k] = (dp[i][j][k] + dp[ni][nj][k - 1]) % MOD;
                            continue;
                        }
                        dp[i][j][k] = (dp[i][j][k] + 1) % MOD;
                    }
                }
            }
        }   
        return dp[startRow][startColumn][maxMove];
    }
}

class Solution:
    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
        # m is rows, n is cols
        cols = n
        rows = m

        memo = {}

        def helper(i: int, j: int, move: int):
            # outside of board
            if (i < 0 or i >= rows) or (j < 0 or j >= cols):
                return 1 if move == 0 else 0
            if move == 0:
                return 0
            # inside the board
            if (i, j, move) in memo:
                return memo[(i, j, move)]
            directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
            paths = 0
            for dx, dy in directions:
                paths = (paths + helper(i + dx, j + dy, move - 1)) % (10**9 + 7)
            memo[(i, j, move)] = paths
            return paths

        count = 0
        for move in range(1, maxMove + 1):
            count = (count + helper(startRow, startColumn, move)) % (10**9 + 7)
        return count