Grids

Shortest Path in a Grid with Obstacles Elimination - LeetCode. leetcode.com . Accessed Jul 21, 2024. Problem You are given an \(m \times n\) grid where each cell is either 0 (empty) or 1 (obstacle). You can move up, down, left, or right from and to an empty cell in one step. Return the minimum number of steps to walk from the upper left corner \((0, 0)\) to the lower-right corner \((m-1, n-1)\) given that you can eliminate at most \(k\) obstacles....

Queen's Attack II. www.hackerrank.com . Accessed Jul 20, 2024. Problem A queen is standing on an \(n \times n\) chess board. The chess board’s rows are numbered from \(1\) to \(n\), going from bottom to top. Its columns are numbered from \(1\) to \(n\), going from left to right. Each square is referenced by a tuple \((r, c)\), describing the row, \(r\), and column, \(c\), where the square is located....

Grid Game - LeetCode. leetcode.com . Accessed Jul 20, 2024. Problem You are given a 0-indexed 2D array grid of size \(2 \times n\), where grid[r][c] represents the number of points at position \((r, c)\) on the matrix. Two robots are playing a game on this matrix. Both robots initially start at \((0, 0)\) and want to reach \((1, n-1)\). Each robot may only move to the right or down....

Problem Starting from the top-left corner, what is the number of possible unique paths to reach the bottom-right corner, if you can only move either down or right at any point in time, and the path cannot include any square that is an obstacle? Solution The addition of obstacles has these implications: I can’t use the combinatorics formula because the problem is no longer easy to define in general terms....

Problem Given an \(M \times N\) integer array grid where grid[i][j] could be: 1 representing the starting square. There is exactly one starting square. 2 representing the ending square. There is exactly one ending square. 0 representing empty squares that we can walk over. -1 representing obstacles that we cannot walk over. Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once....

Problem Starting from the top-left corner, what is the number of possible unique paths to reach the bottom-right corner, if you can only move either down or right at any point in time? Dynamic Programming Solution for Moving Down/Right #dynamic-programming The number of unique paths to grid[r][c] is the number of unique paths to grid[r-1][c] plus the number of unique paths to grid[r][c-1], e.g., 1111 1234 13610 At any given time, we’re interested in two adjacent rows, so our space usage should be at most \(2n\)....