{"title":"Matrix Traversal","description":"","content":"A matrix is a 2D array organized into rows and columns. In programming, we typically represent it as an array of arrays, where the first index selects the row and the second index selects the column.\n\n\n```java\n// A 3x4 matrix (3 rows, 4 columns)\nint[][] matrix = {\n {1, 2, 3, 4}, // Row 0\n {5, 6, 7, 8}, // Row 1\n {9, 10, 11, 12} // Row 2\n};\n\n// Accessing element at row 1, column 2\nint value = matrix[1][2]; // Returns 7\n```\n\n```python\n# A 3x4 matrix (3 rows, 4 columns)\nmatrix = [\n [1, 2, 3, 4], # Row 0\n [5, 6, 7, 8], # Row 1\n [9, 10, 11, 12] # Row 2\n]\n\n# Accessing element at row 1, column 2\nvalue = matrix[1][2] # Returns 7\n```\n\n```cpp\n// A 3x4 matrix (3 rows, 4 columns)\nvector> matrix = {\n\t{1, 2, 3, 4}, // Row 0\n\t{5, 6, 7, 8}, // Row 1\n\t{9, 10, 11, 12} // Row 2\n};\n\n// Accessing element at row 1, column 2\nint value = matrix[1][2]; // Returns 7\n```\n\n```go\npackage main\n\n// A 3x4 matrix (3 rows, 4 columns)\nvar matrix = [][]int{\n\t{1, 2, 3, 4}, // Row 0\n\t{5, 6, 7, 8}, // Row 1\n\t{9, 10, 11, 12}, // Row 2\n}\n\n// Accessing element at row 1, column 2\nvar value = matrix[1][2] // Returns 7\n```\n\n```csharp\n// A 3x4 matrix (3 rows, 4 columns)\nint[][] matrix = {\n\tnew int[] {1, 2, 3, 4}, // Row 0\n\tnew int[] {5, 6, 7, 8}, // Row 1\n\tnew int[] {9, 10, 11, 12} // Row 2\n};\n\n// Accessing element at row 1, column 2\nint value = matrix[1][2]; // Returns 7\n```\n\n```rust\n// A 3x4 matrix (3 rows, 4 columns)\nlet matrix: Vec> = vec![\n vec![1, 2, 3, 4], // Row 0\n vec![5, 6, 7, 8], // Row 1\n vec![9, 10, 11, 12], // Row 2\n];\n\n// Accessing element at row 1, column 2\nlet value: i32 = matrix[1][2]; // Returns 7\n```\n\n```javascript\n// A 3x4 matrix (3 rows, 4 columns)\nconst matrix = [\n [1, 2, 3, 4], // Row 0\n [5, 6, 7, 8], // Row 1\n [9, 10, 11, 12] // Row 2\n];\n\n// Accessing element at row 1, column 2\nconst value = matrix[1][2]; // Returns 7\n```\n\n```typescript\n// A 3x4 matrix (3 rows, 4 columns)\nconst matrix: number[][] = [\n [1, 2, 3, 4], // Row 0\n [5, 6, 7, 8], // Row 1\n [9, 10, 11, 12] // Row 2\n];\n\n// Accessing element at row 1, column 2\nconst value: number = matrix[1][2]; // Returns 7\n```\n\n\nThe dimensions are typically denoted as `m x n` where m is the number of rows and n is the number of columns. Be careful with the terminology: rows go horizontally (left to right) and columns go vertically (top to bottom).\n\nIn the diagram, the purple cell shows position (1, 2) which contains the value 7. Notice that indices are zero-based: the first row is row 0, and the first column is column 0.\n\n---\n\n# Matrix as an Implicit Graph\n\nThe key insight for matrix traversal is that a grid is really just a graph in disguise. Each cell is a node, and adjacent cells (up, down, left, right) are connected by edges. This mental model unlocks all the graph traversal algorithms.\n\n- **Nodes**: Each cell (i, j) is a node\n- **Edges**: Connect to adjacent cells (typically 4 or 8 neighbors)\n- **No explicit edge list**: Neighbors are computed on demand using direction arrays\n\nThis implicit representation is more memory-efficient than storing an adjacency list, and it allows us to use the grid coordinates directly for indexing.\n\n---\n\n# Direction Arrays: The Key to Grid Navigation\n\nThe most important technique for matrix traversal is the **direction array**. Instead of writing separate logic for moving up, down, left, and right, we encode all directions in arrays and iterate through them.\n\n### 4-Directional Movement\n\nFor problems where you can move up, down, left, and right:\n\n\n```java\n// Direction arrays for 4 neighbors\nint[] rowDir = {-1, 1, 0, 0}; // up, down, same, same\nint[] colDir = {0, 0, -1, 1}; // same, same, left, right\n\n// Or as a 2D array\nint[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};\n```\n\n\n\n```mermaid\nflowchart TD\n U[\"(-1, 0)
Up\"]\n C[\"Current
(r, c)\"]\n D[\"(+1, 0)
Down\"]\n L[\"(0, -1)
Left\"]\n R[\"(0, +1)
Right\"]\n\n U --> C\n C --> D\n L --> C\n C --> R\n\n style C fill:#ffa94d,stroke:#000,color:#000\n style U fill:#00ceff,stroke:#000,color:#000\n style D fill:#00ceff,stroke:#000,color:#000\n style L fill:#00ceff,stroke:#000,color:#000\n style R fill:#00ceff,stroke:#000,color:#000\n```\n\n\n### 8-Directional Movement\n\nFor problems that include diagonal movement:\n\n\n```java\n// Direction arrays for 8 neighbors (including diagonals)\nint[][] directions = {\n {-1, 0}, // up\n {1, 0}, // down\n {0, -1}, // left\n {0, 1}, // right\n {-1, -1}, // up-left\n {-1, 1}, // up-right\n {1, -1}, // down-left\n {1, 1} // down-right\n};\n```\n\n\n\n```mermaid\nflowchart TD\n UL[\"(-1,-1)\"]\n U[\"(-1, 0)\"]\n UR[\"(-1,+1)\"]\n L[\"(0, -1)\"]\n C[\"(r, c)\"]\n R[\"(0, +1)\"]\n DL[\"(+1,-1)\"]\n D[\"(+1, 0)\"]\n DR[\"(+1,+1)\"]\n\n UL --> C\n U --> C\n UR --> C\n L --> C\n C --> R\n C --> D\n C --> DL\n C --> DR\n\n style C fill:#ffa94d,stroke:#000,color:#000\n style U fill:#00ceff,stroke:#000,color:#000\n style D fill:#00ceff,stroke:#000,color:#000\n style L fill:#00ceff,stroke:#000,color:#000\n style R fill:#00ceff,stroke:#000,color:#000\n style UL fill:#ffa94d,stroke:#000,color:#000\n style UR fill:#ffa94d,stroke:#000,color:#000\n style DL fill:#ffa94d,stroke:#000,color:#000\n style DR fill:#ffa94d,stroke:#000,color:#000\n```\n\n\n### Using Direction Arrays\n\nHere is how you use direction arrays to explore neighbors:\n\n\n```java\nint rows = grid.length;\nint cols = grid[0].length;\nint[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};\n\n// Starting from cell (row, col)\nfor (int[] dir : directions) {\n int newRow = row + dir[0];\n int newCol = col + dir[1];\n\n // Boundary check\n if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols) {\n // Process neighbor at (newRow, newCol)\n }\n}\n```\n\n```python\nrows = len(grid)\ncols = len(grid[0])\ndirections = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n\n# Starting from cell (row, col)\nfor dr, dc in directions:\n new_row = row + dr\n new_col = col + dc\n\n # Boundary check\n if 0 <= new_row < rows and 0 <= new_col < cols:\n # Process neighbor at (new_row, new_col)\n pass\n```\n\n```cpp\nint rows = grid.size();\nint cols = grid[0].size();\nvector> directions = {\n {-1, 0}, {1, 0}, {0, -1}, {0, 1}\n};\n\n// Starting from cell (row, col)\nfor (auto& dir : directions) {\n int newRow = row + dir.first;\n int newCol = col + dir.second;\n\n // Boundary check\n if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols) {\n // Process neighbor at (newRow, newCol)\n }\n}\n```\n\n```go\npackage main\n\nfunc matrixTraversal(grid [][]int, row int, col int) {\n\trows := len(grid)\n\tcols := len(grid[0])\n\tdirections := [][2]int{\n\t\t{-1, 0}, {1, 0},\n\t\t{0, -1}, {0, 1},\n\t}\n\n\t// Starting from cell (row, col)\n\tfor _, dir := range directions {\n\t\tnewRow := row + dir[0]\n\t\tnewCol := col + dir[1]\n\n\t\t// Boundary check\n\t\tif newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols {\n\t\t\t// Process neighbor at (newRow, newCol)\n\t\t}\n\t}\n}\n```\n\n```csharp\nint rows = grid.Length;\nint cols = grid[0].Length;\nint[][] directions = {\n new int[] {-1, 0}, new int[] {1, 0},\n new int[] {0, -1}, new int[] {0, 1}\n};\n\n// Starting from cell (row, col)\nforeach (var dir in directions) {\n int newRow = row + dir[0];\n int newCol = col + dir[1];\n\n // Boundary check\n if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols) {\n // Process neighbor at (newRow, newCol)\n }\n}\n```\n\n```rust\nimpl Solution {\n pub fn matrix_traversal(grid: Vec>, row: i32, col: i32) {\n let rows = grid.len() as i32;\n let cols = grid[0].len() as i32;\n let directions = [(-1, 0), (1, 0), (0, -1), (0, 1)];\n\n // Starting from cell (row, col)\n for (dr, dc) in directions.iter() {\n let new_row = row + dr;\n let new_col = col + dc;\n\n // Boundary check\n if new_row >= 0 && new_row < rows && new_col >= 0 && new_col < cols {\n // Process neighbor at (new_row, new_col)\n }\n }\n }\n}\n```\n\n```javascript\nconst rows = grid.length;\nconst cols = grid[0].length;\nconst directions = [\n [-1, 0], [1, 0],\n [0, -1], [0, 1]\n];\n\n// Starting from cell (row, col)\nfor (const [dr, dc] of directions) {\n const newRow = row + dr;\n const newCol = col + dc;\n\n // Boundary check\n if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols) {\n // Process neighbor at (newRow, newCol)\n }\n}\n```\n\n```typescript\nconst rows: number = grid.length;\nconst cols: number = grid[0].length;\nconst directions: number[][] = [\n [-1, 0], [1, 0],\n [0, -1], [0, 1]\n];\n\n// Starting from cell (row, col)\nfor (const [dr, dc] of directions) {\n const newRow: number = row + dr;\n const newCol: number = col + dc;\n\n // Boundary check\n if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols) {\n // Process neighbor at (newRow, newCol)\n }\n}\n```\n\n\nThis pattern appears in almost every matrix traversal problem. Memorize it.\n\n---\n\n# Boundary Checking\n\nOne of the most common sources of bugs in matrix problems is going out of bounds. Always check that the new coordinates are valid before accessing the array.\n\n\n```java\n// Always validate before accessing grid[newRow][newCol]\nboolean isValid(int row, int col, int rows, int cols) {\n return row >= 0 && row < rows && col >= 0 && col < cols;\n}\n```\n\n\nA useful helper method makes your code cleaner and less error-prone:\n\n\n```java\nprivate boolean inBounds(int r, int c, int[][] grid) {\n return r >= 0 && r < grid.length && c >= 0 && c < grid[0].length;\n}\n```\n\n\n---\n\n# Matrix Traversal Patterns\n\nThere are several ways to traverse a matrix, each useful for different problems.\n\n### Linear Traversal\n\nThe simplest approach: visit every cell in row-major or column-major order.\n\n\n```java\n// Row-major: left to right, top to bottom\nfor (int r = 0; r < rows; r++) {\n for (int c = 0; c < cols; c++) {\n process(grid[r][c]);\n }\n}\n\n// Column-major: top to bottom, left to right\nfor (int c = 0; c < cols; c++) {\n for (int r = 0; r < rows; r++) {\n process(grid[r][c]);\n }\n}\n```\n\n\n**Use when**: You need to process every cell once, like counting elements or finding a specific value.\n\n### Diagonal Traversal\n\nVisit cells along diagonals. Useful for problems involving diagonal patterns.\n\n\n```java\n// Main diagonal and parallel diagonals\nfor (int d = 0; d < rows + cols - 1; d++) {\n int r = Math.max(0, d - cols + 1);\n int c = Math.max(0, cols - 1 - d);\n while (r < rows && c < cols) {\n process(grid[r][c]);\n r++;\n c++;\n }\n}\n```\n\n\n### Spiral Traversal\n\nVisit cells in a spiral pattern, starting from the outer edge and moving inward.\n\n\n```java\npublic List spiralOrder(int[][] matrix) {\n List result = new ArrayList<>();\n if (matrix.length == 0) return result;\n\n int top = 0, bottom = matrix.length - 1;\n int left = 0, right = matrix[0].length - 1;\n\n while (top <= bottom && left <= right) {\n // Move right\n for (int c = left; c <= right; c++) {\n result.add(matrix[top][c]);\n }\n top++;\n\n // Move down\n for (int r = top; r <= bottom; r++) {\n result.add(matrix[r][right]);\n }\n right--;\n\n // Move left\n if (top <= bottom) {\n for (int c = right; c >= left; c--) {\n result.add(matrix[bottom][c]);\n }\n bottom--;\n }\n\n // Move up\n if (left <= right) {\n for (int r = bottom; r >= top; r--) {\n result.add(matrix[r][left]);\n }\n left++;\n }\n }\n return result;\n}\n```\n\n```python\ndef spiralOrder(matrix):\n result = []\n if not matrix:\n return result\n\n top, bottom = 0, len(matrix) - 1\n left, right = 0, len(matrix[0]) - 1\n\n while top <= bottom and left <= right:\n # Move right\n for c in range(left, right + 1):\n result.append(matrix[top][c])\n top += 1\n\n # Move down\n for r in range(top, bottom + 1):\n result.append(matrix[r][right])\n right -= 1\n\n # Move left\n if top <= bottom:\n for c in range(right, left - 1, -1):\n result.append(matrix[bottom][c])\n bottom -= 1\n\n # Move up\n if left <= right:\n for r in range(bottom, top - 1, -1):\n result.append(matrix[r][left])\n left += 1\n\n return result\n```\n\n```cpp\nvector spiralOrder(vector>& matrix) {\n vector result;\n if (matrix.empty()) return result;\n\n int top = 0, bottom = matrix.size() - 1;\n int left = 0, right = matrix[0].size() - 1;\n\n while (top <= bottom && left <= right) {\n // Move right\n for (int c = left; c <= right; c++) {\n result.push_back(matrix[top][c]);\n }\n top++;\n\n // Move down\n for (int r = top; r <= bottom; r++) {\n result.push_back(matrix[r][right]);\n }\n right--;\n\n // Move left\n if (top <= bottom) {\n for (int c = right; c >= left; c--) {\n result.push_back(matrix[bottom][c]);\n }\n bottom--;\n }\n\n // Move up\n if (left <= right) {\n for (int r = bottom; r >= top; r--) {\n result.push_back(matrix[r][left]);\n }\n left++;\n }\n }\n return result;\n}\n```\n\n```go\npackage main\n\nfunc spiralOrder(matrix [][]int) []int {\n\tresult := []int{}\n\tif len(matrix) == 0 {\n\t\treturn result\n\t}\n\n\ttop, bottom := 0, len(matrix)-1\n\tleft, right := 0, len(matrix[0])-1\n\n\tfor top <= bottom && left <= right {\n\t\t// Move right\n\t\tfor c := left; c <= right; c++ {\n\t\t\tresult = append(result, matrix[top][c])\n\t\t}\n\t\ttop++\n\n\t\t// Move down\n\t\tfor r := top; r <= bottom; r++ {\n\t\t\tresult = append(result, matrix[r][right])\n\t\t}\n\t\tright--\n\n\t\t// Move left\n\t\tif top <= bottom {\n\t\t\tfor c := right; c >= left; c-- {\n\t\t\t\tresult = append(result, matrix[bottom][c])\n\t\t\t}\n\t\t\tbottom--\n\t\t}\n\n\t\t// Move up\n\t\tif left <= right {\n\t\t\tfor r := bottom; r >= top; r-- {\n\t\t\t\tresult = append(result, matrix[r][left])\n\t\t\t}\n\t\t\tleft++\n\t\t}\n\t}\n\n\treturn result\n}\n```\n\n```csharp\npublic IList SpiralOrder(int[][] matrix) {\n\tvar result = new List();\n\tif (matrix.Length == 0) return result;\n\n\tint top = 0, bottom = matrix.Length - 1;\n\tint left = 0, right = matrix[0].Length - 1;\n\n\twhile (top <= bottom && left <= right) {\n\t\t// Move right\n\t\tfor (int c = left; c <= right; c++) {\n\t\t\tresult.Add(matrix[top][c]);\n\t\t}\n\t\ttop++;\n\n\t\t// Move down\n\t\tfor (int r = top; r <= bottom; r++) {\n\t\t\tresult.Add(matrix[r][right]);\n\t\t}\n\t\tright--;\n\n\t\t// Move left\n\t\tif (top <= bottom) {\n\t\t\tfor (int c = right; c >= left; c--) {\n\t\t\t\tresult.Add(matrix[bottom][c]);\n\t\t\t}\n\t\t\tbottom--;\n\t\t}\n\n\t\t// Move up\n\t\tif (left <= right) {\n\t\t\tfor (int r = bottom; r >= top; r--) {\n\t\t\t\tresult.Add(matrix[r][left]);\n\t\t\t}\n\t\t\tleft++;\n\t\t}\n\t}\n\n\treturn result;\n}\n```\n\n```rust\npub struct Solution;\n\nimpl Solution {\n pub fn spiral_order(matrix: Vec>) -> Vec {\n let mut result = Vec::new();\n if matrix.is_empty() {\n return result;\n }\n\n let mut top: i32 = 0;\n let mut bottom: i32 = matrix.len() as i32 - 1;\n let mut left: i32 = 0;\n let mut right: i32 = matrix[0].len() as i32 - 1;\n\n while top <= bottom && left <= right {\n // Move right\n for c in left..=right {\n result.push(matrix[top as usize][c as usize]);\n }\n top += 1;\n\n // Move down\n for r in top..=bottom {\n result.push(matrix[r as usize][right as usize]);\n }\n right -= 1;\n\n // Move left\n if top <= bottom {\n for c in (left..=right).rev() {\n result.push(matrix[bottom as usize][c as usize]);\n }\n bottom -= 1;\n }\n\n // Move up\n if left <= right {\n for r in (top..=bottom).rev() {\n result.push(matrix[r as usize][left as usize]);\n }\n left += 1;\n }\n }\n\n result\n }\n}\n```\n\n```javascript\nfunction spiralOrder(matrix) {\n const result = [];\n if (matrix.length === 0) return result;\n\n let top = 0, bottom = matrix.length - 1;\n let left = 0, right = matrix[0].length - 1;\n\n while (top <= bottom && left <= right) {\n // Move right\n for (let c = left; c <= right; c++) {\n result.push(matrix[top][c]);\n }\n top++;\n\n // Move down\n for (let r = top; r <= bottom; r++) {\n result.push(matrix[r][right]);\n }\n right--;\n\n // Move left\n if (top <= bottom) {\n for (let c = right; c >= left; c--) {\n result.push(matrix[bottom][c]);\n }\n bottom--;\n }\n\n // Move up\n if (left <= right) {\n for (let r = bottom; r >= top; r--) {\n result.push(matrix[r][left]);\n }\n left++;\n }\n }\n\n return result;\n}\n```\n\n```typescript\nfunction spiralOrder(matrix: number[][]): number[] {\n const result: number[] = [];\n if (matrix.length === 0) return result;\n\n let top = 0, bottom = matrix.length - 1;\n let left = 0, right = matrix[0].length - 1;\n\n while (top <= bottom && left <= right) {\n // Move right\n for (let c = left; c <= right; c++) {\n result.push(matrix[top][c]);\n }\n top++;\n\n // Move down\n for (let r = top; r <= bottom; r++) {\n result.push(matrix[r][right]);\n }\n right--;\n\n // Move left\n if (top <= bottom) {\n for (let c = right; c >= left; c--) {\n result.push(matrix[bottom][c]);\n }\n bottom--;\n }\n\n // Move up\n if (left <= right) {\n for (let r = bottom; r >= top; r--) {\n result.push(matrix[r][left]);\n }\n left++;\n }\n }\n\n return result;\n}\n```\n\n\n### DFS and BFS Traversal\n\nThe most powerful patterns for matrix problems. These treat the grid as a graph and explore it using standard graph algorithms.\n\n---\n\n# DFS on Grids\n\nDepth-First Search explores as far as possible along each branch before backtracking. On a grid, this means going in one direction until you hit a boundary or obstacle, then trying another direction.\n\n### Recursive DFS Template\n\n\n```java\nprivate void dfs(int[][] grid, int row, int col, boolean[][] visited) {\n int rows = grid.length;\n int cols = grid[0].length;\n\n // Base case: out of bounds or already visited\n if (row < 0 || row >= rows || col < 0 || col >= cols) {\n return;\n }\n if (visited[row][col]) {\n return;\n }\n\n // Mark as visited\n visited[row][col] = true;\n\n // Process current cell\n // ... (problem-specific logic)\n\n // Explore all 4 directions\n int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};\n for (int[] dir : directions) {\n dfs(grid, row + dir[0], col + dir[1], visited);\n }\n}\n```\n\n```python\ndef dfs(grid, row, col, visited):\n rows, cols = len(grid), len(grid[0])\n\n # Base case: out of bounds or already visited\n if row < 0 or row >= rows or col < 0 or col >= cols:\n return\n if visited[row][col]:\n return\n\n # Mark as visited\n visited[row][col] = True\n\n # Process current cell\n # ... (problem-specific logic)\n\n # Explore all 4 directions\n directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n for dr, dc in directions:\n dfs(grid, row + dr, col + dc, visited)\n```\n\n```cpp\nvoid dfs(vector>& grid, int row, int col, vector>& visited) {\n int rows = grid.size();\n int cols = grid[0].size();\n\n // Base case: out of bounds or already visited\n if (row < 0 || row >= rows || col < 0 || col >= cols) {\n return;\n }\n if (visited[row][col]) {\n return;\n }\n\n // Mark as visited\n visited[row][col] = true;\n\n // Process current cell\n // ... (problem-specific logic)\n\n // Explore all 4 directions\n vector> directions = {\n {-1, 0}, {1, 0}, {0, -1}, {0, 1}\n };\n for (auto& dir : directions) {\n dfs(grid, row + dir.first, col + dir.second, visited);\n }\n}\n```\n\n```go\npackage main\n\nfunc dfs(grid [][]int, row int, col int, visited [][]bool) {\n\trows := len(grid)\n\tcols := len(grid[0])\n\n\t// Base case: out of bounds or already visited\n\tif row < 0 || row >= rows || col < 0 || col >= cols {\n\t\treturn\n\t}\n\tif visited[row][col] {\n\t\treturn\n\t}\n\n\t// Mark as visited\n\tvisited[row][col] = true\n\n\t// Process current cell\n\t// ... (problem-specific logic)\n\n\t// Explore all 4 directions\n\tdirections := [][]int{\n\t\t{-1, 0}, {1, 0},\n\t\t{0, -1}, {0, 1},\n\t}\n\n\tfor _, dir := range directions {\n\t\tdfs(grid, row+dir[0], col+dir[1], visited)\n\t}\n}\n```\n\n```csharp\npublic void Dfs(int[][] grid, int row, int col, bool[][] visited) {\n int rows = grid.Length;\n int cols = grid[0].Length;\n\n // Base case: out of bounds or already visited\n if (row < 0 || row >= rows || col < 0 || col >= cols) {\n return;\n }\n if (visited[row][col]) {\n return;\n }\n\n // Mark as visited\n visited[row][col] = true;\n\n // Process current cell\n // ... (problem-specific logic)\n\n // Explore all 4 directions\n int[][] directions = {\n new int[] {-1, 0}, new int[] {1, 0},\n new int[] {0, -1}, new int[] {0, 1}\n };\n\n foreach (var dir in directions) {\n Dfs(grid, row + dir[0], col + dir[1], visited);\n }\n}\n```\n\n```rust\npub struct Solution;\n\nimpl Solution {\n pub fn dfs(grid: Vec>, row: i32, col: i32, visited: &mut Vec>) {\n let rows = grid.len() as i32;\n let cols = grid[0].len() as i32;\n\n // Base case: out of bounds or already visited\n if row < 0 || row >= rows || col < 0 || col >= cols {\n return;\n }\n let r = row as usize;\n let c = col as usize;\n if visited[r][c] {\n return;\n }\n\n // Mark as visited\n visited[r][c] = true;\n\n // Process current cell\n // ... (problem-specific logic)\n\n // Explore all 4 directions\n let directions: [(i32, i32); 4] = [(-1, 0), (1, 0), (0, -1), (0, 1)];\n for (dr, dc) in directions {\n Self::dfs(grid.clone(), row + dr, col + dc, visited);\n }\n }\n}\n```\n\n```javascript\nfunction dfs(grid, row, col, visited) {\n const rows = grid.length;\n const cols = grid[0].length;\n\n // Base case: out of bounds or already visited\n if (row < 0 || row >= rows || col < 0 || col >= cols) {\n return;\n }\n if (visited[row][col]) {\n return;\n }\n\n // Mark as visited\n visited[row][col] = true;\n\n // Process current cell\n // ... (problem-specific logic)\n\n // Explore all 4 directions\n const directions = [\n [-1, 0], [1, 0],\n [0, -1], [0, 1]\n ];\n\n for (const [dr, dc] of directions) {\n dfs(grid, row + dr, col + dc, visited);\n }\n}\n```\n\n```typescript\nfunction dfs(\n grid: number[][],\n row: number,\n col: number,\n visited: boolean[][]\n): void {\n const rows: number = grid.length;\n const cols: number = grid[0].length;\n\n // Base case: out of bounds or already visited\n if (row < 0 || row >= rows || col < 0 || col >= cols) {\n return;\n }\n if (visited[row][col]) {\n return;\n }\n\n // Mark as visited\n visited[row][col] = true;\n\n // Process current cell\n // ... (problem-specific logic)\n\n // Explore all 4 directions\n const directions: number[][] = [\n [-1, 0], [1, 0],\n [0, -1], [0, 1]\n ];\n\n for (const [dr, dc] of directions) {\n dfs(grid, row + dr, col + dc, visited);\n }\n}\n```\n\n\n### Iterative DFS Template (Using Stack)\n\n\n```java\nprivate void dfsIterative(int[][] grid, int startRow, int startCol) {\n int rows = grid.length;\n int cols = grid[0].length;\n boolean[][] visited = new boolean[rows][cols];\n\n Stack stack = new Stack<>();\n stack.push(new int[]{startRow, startCol});\n\n int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};\n\n while (!stack.isEmpty()) {\n int[] cell = stack.pop();\n int row = cell[0];\n int col = cell[1];\n\n if (row < 0 || row >= rows || col < 0 || col >= cols) {\n continue;\n }\n if (visited[row][col]) {\n continue;\n }\n\n visited[row][col] = true;\n // Process current cell\n\n for (int[] dir : directions) {\n stack.push(new int[]{row + dir[0], col + dir[1]});\n }\n }\n}\n```\n\n```python\ndef dfs_iterative(grid, start_row, start_col):\n rows, cols = len(grid), len(grid[0])\n visited = [[False] * cols for _ in range(rows)]\n\n stack = [(start_row, start_col)]\n directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n\n while stack:\n row, col = stack.pop()\n\n if row < 0 or row >= rows or col < 0 or col >= cols:\n continue\n if visited[row][col]:\n continue\n\n visited[row][col] = True\n # Process current cell\n\n for dr, dc in directions:\n stack.append((row + dr, col + dc))\n```\n\n```cpp\nvoid dfsIterative(vector>& grid, int startRow, int startCol) {\n int rows = grid.size();\n int cols = grid[0].size();\n vector> visited(rows, vector(cols, false));\n\n stack> st;\n st.push({startRow, startCol});\n\n vector> directions = {\n {-1, 0}, {1, 0}, {0, -1}, {0, 1}\n };\n\n while (!st.empty()) {\n auto [row, col] = st.top();\n st.pop();\n\n if (row < 0 || row >= rows || col < 0 || col >= cols) {\n continue;\n }\n if (visited[row][col]) {\n continue;\n }\n\n visited[row][col] = true;\n // Process current cell\n\n for (auto& dir : directions) {\n st.push({row + dir.first, col + dir.second});\n }\n }\n}\n```\n\n```go\npackage main\n\nfunc dfsIterative(grid [][]int, startRow int, startCol int) {\n\trows := len(grid)\n\tcols := len(grid[0])\n\tvisited := make([][]bool, rows)\n\tfor i := 0; i < rows; i++ {\n\t\tvisited[i] = make([]bool, cols)\n\t}\n\n\tstack := [][2]int{{startRow, startCol}}\n\n\tdirections := [][2]int{\n\t\t{-1, 0}, {1, 0},\n\t\t{0, -1}, {0, 1},\n\t}\n\n\tfor len(stack) > 0 {\n\t\tcell := stack[len(stack)-1]\n\t\tstack = stack[:len(stack)-1]\n\t\trow, col := cell[0], cell[1]\n\n\t\tif row < 0 || row >= rows || col < 0 || col >= cols {\n\t\t\tcontinue\n\t\t}\n\t\tif visited[row][col] {\n\t\t\tcontinue\n\t\t}\n\n\t\tvisited[row][col] = true\n\t\t// Process current cell\n\n\t\tfor _, dir := range directions {\n\t\t\tstack = append(stack, [2]int{row + dir[0], col + dir[1]})\n\t\t}\n\t}\n}\n```\n\n```csharp\npublic void DfsIterative(int[][] grid, int startRow, int startCol) {\n int rows = grid.Length;\n int cols = grid[0].Length;\n bool[][] visited = new bool[rows][];\n for (int i = 0; i < rows; i++) {\n visited[i] = new bool[cols];\n }\n\n Stack<(int, int)> stack = new Stack<(int, int)>();\n stack.Push((startRow, startCol));\n\n int[][] directions = {\n new int[] {-1, 0}, new int[] {1, 0},\n new int[] {0, -1}, new int[] {0, 1}\n };\n\n while (stack.Count > 0) {\n var (row, col) = stack.Pop();\n\n if (row < 0 || row >= rows || col < 0 || col >= cols) {\n continue;\n }\n if (visited[row][col]) {\n continue;\n }\n\n visited[row][col] = true;\n // Process current cell\n\n foreach (var dir in directions) {\n stack.Push((row + dir[0], col + dir[1]));\n }\n }\n}\n```\n\n```rust\npub struct Solution;\n\nimpl Solution {\n pub fn dfs_iterative(grid: Vec>, start_row: i32, start_col: i32) {\n let rows = grid.len() as i32;\n let cols = grid[0].len() as i32;\n let mut visited = vec![vec![false; cols as usize]; rows as usize];\n\n let mut stack: Vec<(i32, i32)> = vec![(start_row, start_col)];\n\n let directions = [(-1, 0), (1, 0), (0, -1), (0, 1)];\n\n while let Some((row, col)) = stack.pop() {\n if row < 0 || row >= rows || col < 0 || col >= cols {\n continue;\n }\n if visited[row as usize][col as usize] {\n continue;\n }\n\n visited[row as usize][col as usize] = true;\n // Process current cell\n\n for (dr, dc) in directions.iter() {\n stack.push((row + dr, col + dc));\n }\n }\n }\n}\n```\n\n```javascript\nfunction dfsIterative(grid, startRow, startCol) {\n const rows = grid.length;\n const cols = grid[0].length;\n const visited = Array.from({ length: rows }, () => Array(cols).fill(false));\n\n const stack = [[startRow, startCol]];\n const directions = [\n [-1, 0], [1, 0],\n [0, -1], [0, 1]\n ];\n\n while (stack.length > 0) {\n const [row, col] = stack.pop();\n\n if (row < 0 || row >= rows || col < 0 || col >= cols) {\n continue;\n }\n if (visited[row][col]) {\n continue;\n }\n\n visited[row][col] = true;\n // Process current cell\n\n for (const [dr, dc] of directions) {\n stack.push([row + dr, col + dc]);\n }\n }\n}\n```\n\n```typescript\nfunction dfsIterative(grid: number[][], startRow: number, startCol: number): void {\n const rows: number = grid.length;\n const cols: number = grid[0].length;\n const visited: boolean[][] = Array.from({ length: rows }, () => Array(cols).fill(false));\n\n const stack: [number, number][] = [[startRow, startCol]];\n const directions: number[][] = [\n [-1, 0], [1, 0],\n [0, -1], [0, 1]\n ];\n\n while (stack.length > 0) {\n const [row, col] = stack.pop()!;\n\n if (row < 0 || row >= rows || col < 0 || col >= cols) {\n continue;\n }\n if (visited[row][col]) {\n continue;\n }\n\n visited[row][col] = true;\n // Process current cell\n\n for (const [dr, dc] of directions) {\n stack.push([row + dr, col + dc]);\n }\n }\n}\n```\n\n\n### In-Place Marking\n\nFor many problems, instead of using a separate visited array, you can modify the grid itself to mark visited cells. This saves space.\n\n\n```java\nprivate void dfs(char[][] grid, int row, int col) {\n int rows = grid.length;\n int cols = grid[0].length;\n\n if (row < 0 || row >= rows || col < 0 || col >= cols) {\n return;\n }\n if (grid[row][col] != '1') { // Already visited or not valid\n return;\n }\n\n // Mark as visited by changing the value\n grid[row][col] = '0'; // or '#' or any sentinel value\n\n // Explore neighbors\n dfs(grid, row - 1, col);\n dfs(grid, row + 1, col);\n dfs(grid, row, col - 1);\n dfs(grid, row, col + 1);\n}\n```\n\n```python\ndef dfs(grid, row, col):\n rows, cols = len(grid), len(grid[0])\n\n if row < 0 or row >= rows or col < 0 or col >= cols:\n return\n if grid[row][col] != '1': # Already visited or not valid\n return\n\n # Mark as visited\n grid[row][col] = '0' # or '#'\n\n # Explore neighbors\n dfs(grid, row - 1, col)\n dfs(grid, row + 1, col)\n dfs(grid, row, col - 1)\n dfs(grid, row, col + 1)\n```\n\n```cpp\nvoid dfs(vector>& grid, int row, int col) {\n int rows = grid.size();\n int cols = grid[0].size();\n\n if (row < 0 || row >= rows || col < 0 || col >= cols) {\n return;\n }\n if (grid[row][col] != '1') { // Already visited or not valid\n return;\n }\n\n // Mark as visited\n grid[row][col] = '0'; // or '#'\n\n // Explore neighbors\n dfs(grid, row - 1, col);\n dfs(grid, row + 1, col);\n dfs(grid, row, col - 1);\n dfs(grid, row, col + 1);\n}\n```\n\n```go\npackage main\n\nfunc dfs(grid [][]byte, row int, col int) {\n\trows := len(grid)\n\tcols := len(grid[0])\n\n\tif row < 0 || row >= rows || col < 0 || col >= cols {\n\t\treturn\n\t}\n\tif grid[row][col] != '1' { // Already visited or not valid\n\t\treturn\n\t}\n\n\t// Mark as visited\n\tgrid[row][col] = '0' // or '#'\n\n\t// Explore neighbors\n\tdfs(grid, row-1, col)\n\tdfs(grid, row+1, col)\n\tdfs(grid, row, col-1)\n\tdfs(grid, row, col+1)\n}\n```\n\n```csharp\npublic void Dfs(char[][] grid, int row, int col) {\n int rows = grid.Length;\n int cols = grid[0].Length;\n\n if (row < 0 || row >= rows || col < 0 || col >= cols) {\n return;\n }\n if (grid[row][col] != '1') { // Already visited or not valid\n return;\n }\n\n // Mark as visited\n grid[row][col] = '0'; // or '#'\n\n // Explore neighbors\n Dfs(grid, row - 1, col);\n Dfs(grid, row + 1, col);\n Dfs(grid, row, col - 1);\n Dfs(grid, row, col + 1);\n}\n```\n\n```rust\npub struct Solution;\n\nimpl Solution {\n pub fn dfs(grid: &mut Vec>, row: i32, col: i32) {\n let rows = grid.len() as i32;\n let cols = grid[0].len() as i32;\n\n if row < 0 || row >= rows || col < 0 || col >= cols {\n return;\n }\n if grid[row as usize][col as usize] != '1' { // Already visited or not valid\n return;\n }\n\n // Mark as visited\n grid[row as usize][col as usize] = '0'; // or '#'\n\n // Explore neighbors\n Self::dfs(grid, row - 1, col);\n Self::dfs(grid, row + 1, col);\n Self::dfs(grid, row, col - 1);\n Self::dfs(grid, row, col + 1);\n }\n}\n```\n\n```javascript\nfunction dfs(grid, row, col) {\n const rows = grid.length;\n const cols = grid[0].length;\n\n if (row < 0 || row >= rows || col < 0 || col >= cols) {\n return;\n }\n if (grid[row][col] !== '1') { // Already visited or not valid\n return;\n }\n\n // Mark as visited\n grid[row][col] = '0'; // or '#'\n\n // Explore neighbors\n dfs(grid, row - 1, col);\n dfs(grid, row + 1, col);\n dfs(grid, row, col - 1);\n dfs(grid, row, col + 1);\n}\n```\n\n```typescript\nfunction dfs(grid: string[][], row: number, col: number): void {\n const rows: number = grid.length;\n const cols: number = grid[0].length;\n\n if (row < 0 || row >= rows || col < 0 || col >= cols) {\n return;\n }\n if (grid[row][col] !== '1') { // Already visited or not valid\n return;\n }\n\n // Mark as visited\n grid[row][col] = '0'; // or '#'\n\n // Explore neighbors\n dfs(grid, row - 1, col);\n dfs(grid, row + 1, col);\n dfs(grid, row, col - 1);\n dfs(grid, row, col + 1);\n}\n```\n\n\n**Warning**: In-place modification changes the input. Only use this when the problem allows it or when you make a copy first.\n\n---\n\n# BFS on Grids\n\nBreadth-First Search explores all neighbors at the current depth before moving to the next level. On a grid, this means exploring all cells at distance 1, then all cells at distance 2, and so on.\n\n### BFS Template\n\n\n```java\nprivate void bfs(int[][] grid, int startRow, int startCol) {\n int rows = grid.length;\n int cols = grid[0].length;\n boolean[][] visited = new boolean[rows][cols];\n\n Queue queue = new LinkedList<>();\n queue.offer(new int[]{startRow, startCol});\n visited[startRow][startCol] = true;\n\n int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};\n\n while (!queue.isEmpty()) {\n int[] cell = queue.poll();\n int row = cell[0];\n int col = cell[1];\n\n // Process current cell\n // ... (problem-specific logic)\n\n for (int[] dir : directions) {\n int newRow = row + dir[0];\n int newCol = col + dir[1];\n\n if (newRow >= 0 && newRow < rows &&\n newCol >= 0 && newCol < cols &&\n !visited[newRow][newCol]) {\n\n visited[newRow][newCol] = true; // Mark visited when adding to queue\n queue.offer(new int[]{newRow, newCol});\n }\n }\n }\n}\n```\n\n```python\nfrom collections import deque\n\ndef bfs(grid, start_row, start_col):\n rows, cols = len(grid), len(grid[0])\n visited = [[False] * cols for _ in range(rows)]\n\n queue = deque()\n queue.append((start_row, start_col))\n visited[start_row][start_col] = True\n\n directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n\n while queue:\n row, col = queue.popleft()\n\n # Process current cell\n # ... (problem-specific logic)\n\n for dr, dc in directions:\n new_row = row + dr\n new_col = col + dc\n\n if (0 <= new_row < rows and\n 0 <= new_col < cols and\n not visited[new_row][new_col]):\n\n visited[new_row][new_col] = True\n queue.append((new_row, new_col))\n```\n\n```cpp\nvoid bfs(vector>& grid, int startRow, int startCol) {\n int rows = grid.size();\n int cols = grid[0].size();\n vector> visited(rows, vector(cols, false));\n\n queue> q;\n q.push({startRow, startCol});\n visited[startRow][startCol] = true;\n\n vector> directions = {\n {-1, 0}, {1, 0}, {0, -1}, {0, 1}\n };\n\n while (!q.empty()) {\n auto [row, col] = q.front();\n q.pop();\n\n // Process current cell\n // ... (problem-specific logic)\n\n for (auto& dir : directions) {\n int newRow = row + dir.first;\n int newCol = col + dir.second;\n\n if (newRow >= 0 && newRow < rows &&\n newCol >= 0 && newCol < cols &&\n !visited[newRow][newCol]) {\n\n visited[newRow][newCol] = true;\n q.push({newRow, newCol});\n }\n }\n }\n}\n```\n\n```go\npackage main\n\nfunc bfs(grid [][]int, startRow int, startCol int) {\n\trows := len(grid)\n\tcols := len(grid[0])\n\tvisited := make([][]bool, rows)\n\tfor i := 0; i < rows; i++ {\n\t\tvisited[i] = make([]bool, cols)\n\t}\n\n\tqueue := make([][2]int, 0)\n\tqueue = append(queue, [2]int{startRow, startCol})\n\tvisited[startRow][startCol] = true\n\n\tdirections := [][2]int{\n\t\t{-1, 0}, {1, 0}, {0, -1}, {0, 1},\n\t}\n\n\tfor head := 0; head < len(queue); head++ {\n\t\tcell := queue[head]\n\t\trow := cell[0]\n\t\tcol := cell[1]\n\n\t\t// Process current cell\n\t\t// ... (problem-specific logic)\n\n\t\tfor _, dir := range directions {\n\t\t\tnewRow := row + dir[0]\n\t\t\tnewCol := col + dir[1]\n\n\t\t\tif newRow >= 0 && newRow < rows &&\n\t\t\t\tnewCol >= 0 && newCol < cols &&\n\t\t\t\t!visited[newRow][newCol] {\n\n\t\t\t\tvisited[newRow][newCol] = true // Mark visited when adding to queue\n\t\t\t\tqueue = append(queue, [2]int{newRow, newCol})\n\t\t\t}\n\t\t}\n\t}\n}\n```\n\n```csharp\npublic void Bfs(int[][] grid, int startRow, int startCol) {\n int rows = grid.Length;\n int cols = grid[0].Length;\n bool[][] visited = new bool[rows][];\n for (int i = 0; i < rows; i++) {\n visited[i] = new bool[cols];\n }\n\n Queue<(int, int)> queue = new Queue<(int, int)>();\n queue.Enqueue((startRow, startCol));\n visited[startRow][startCol] = true;\n\n int[][] directions = {\n new int[] {-1, 0}, new int[] {1, 0},\n new int[] {0, -1}, new int[] {0, 1}\n };\n\n while (queue.Count > 0) {\n var (row, col) = queue.Dequeue();\n\n // Process current cell\n // ... (problem-specific logic)\n\n foreach (var dir in directions) {\n int newRow = row + dir[0];\n int newCol = col + dir[1];\n\n if (newRow >= 0 && newRow < rows &&\n newCol >= 0 && newCol < cols &&\n !visited[newRow][newCol]) {\n\n visited[newRow][newCol] = true;\n queue.Enqueue((newRow, newCol));\n }\n }\n }\n}\n```\n\n```rust\nuse std::collections::VecDeque;\n\npub struct Solution;\n\nimpl Solution {\n pub fn bfs(grid: Vec>, start_row: i32, start_col: i32) {\n let rows = grid.len();\n let cols = grid[0].len();\n let mut visited = vec![vec![false; cols]; rows];\n\n let mut queue: VecDeque<(usize, usize)> = VecDeque::new();\n let sr = start_row as usize;\n let sc = start_col as usize;\n queue.push_back((sr, sc));\n visited[sr][sc] = true;\n\n let directions: [(i32, i32); 4] = [(-1, 0), (1, 0), (0, -1), (0, 1)];\n\n while let Some((row, col)) = queue.pop_front() {\n // Process current cell\n // ... (problem-specific logic)\n\n for (dr, dc) in directions.iter() {\n let new_row = row as i32 + dr;\n let new_col = col as i32 + dc;\n\n if new_row >= 0\n && new_row < rows as i32\n && new_col >= 0\n && new_col < cols as i32\n && !visited[new_row as usize][new_col as usize]\n {\n visited[new_row as usize][new_col as usize] = true; // Mark visited when adding to queue\n queue.push_back((new_row as usize, new_col as usize));\n }\n }\n }\n }\n}\n```\n\n```javascript\nfunction bfs(grid, startRow, startCol) {\n const rows = grid.length;\n const cols = grid[0].length;\n const visited = Array.from({ length: rows }, () => Array(cols).fill(false));\n\n const queue = [];\n queue.push([startRow, startCol]);\n visited[startRow][startCol] = true;\n\n const directions = [\n [-1, 0], [1, 0],\n [0, -1], [0, 1]\n ];\n\n while (queue.length > 0) {\n const [row, col] = queue.shift();\n\n // Process current cell\n // ... (problem-specific logic)\n\n for (const [dr, dc] of directions) {\n const newRow = row + dr;\n const newCol = col + dc;\n\n if (newRow >= 0 && newRow < rows &&\n newCol >= 0 && newCol < cols &&\n !visited[newRow][newCol]) {\n\n visited[newRow][newCol] = true;\n queue.push([newRow, newCol]);\n }\n }\n }\n}\n```\n\n```typescript\nfunction bfs(grid: number[][], startRow: number, startCol: number): void {\n const rows: number = grid.length;\n const cols: number = grid[0].length;\n const visited: boolean[][] = Array.from({ length: rows }, () => Array(cols).fill(false));\n\n const queue: [number, number][] = [];\n queue.push([startRow, startCol]);\n visited[startRow][startCol] = true;\n\n const directions: number[][] = [\n [-1, 0], [1, 0],\n [0, -1], [0, 1]\n ];\n\n while (queue.length > 0) {\n const [row, col] = queue.shift()!;\n\n // Process current cell\n // ... (problem-specific logic)\n\n for (const [dr, dc] of directions) {\n const newRow: number = row + dr;\n const newCol: number = col + dc;\n\n if (newRow >= 0 && newRow < rows &&\n newCol >= 0 && newCol < cols &&\n !visited[newRow][newCol]) {\n\n visited[newRow][newCol] = true;\n queue.push([newRow, newCol]);\n }\n }\n }\n}\n```\n\n\n### BFS for Shortest Path\n\nBFS naturally finds the shortest path in an unweighted graph. To track the distance, process the queue level by level:\n\n\n```java\nprivate int shortestPath(int[][] grid, int startRow, int startCol, int endRow, int endCol) {\n int rows = grid.length;\n int cols = grid[0].length;\n boolean[][] visited = new boolean[rows][cols];\n\n Queue queue = new LinkedList<>();\n queue.offer(new int[]{startRow, startCol});\n visited[startRow][startCol] = true;\n\n int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};\n int distance = 0;\n\n while (!queue.isEmpty()) {\n int size = queue.size(); // Process one level at a time\n\n for (int i = 0; i < size; i++) {\n int[] cell = queue.poll();\n int row = cell[0];\n int col = cell[1];\n\n if (row == endRow && col == endCol) {\n return distance;\n }\n\n for (int[] dir : directions) {\n int newRow = row + dir[0];\n int newCol = col + dir[1];\n\n if (newRow >= 0 && newRow < rows &&\n newCol >= 0 && newCol < cols &&\n !visited[newRow][newCol] &&\n grid[newRow][newCol] != 1) { // 1 represents obstacle\n\n visited[newRow][newCol] = true;\n queue.offer(new int[]{newRow, newCol});\n }\n }\n }\n distance++;\n }\n\n return -1; // No path found\n}\n```\n\n```python\nfrom collections import deque\n\ndef shortest_path(grid, start_row, start_col, end_row, end_col):\n rows, cols = len(grid), len(grid[0])\n visited = [[False] * cols for _ in range(rows)]\n\n queue = deque()\n queue.append((start_row, start_col))\n visited[start_row][start_col] = True\n\n directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n distance = 0\n\n while queue:\n size = len(queue) # Process one level at a time\n\n for _ in range(size):\n row, col = queue.popleft()\n\n if row == end_row and col == end_col:\n return distance\n\n for dr, dc in directions:\n new_row = row + dr\n new_col = col + dc\n\n if (0 <= new_row < rows and\n 0 <= new_col < cols and\n not visited[new_row][new_col] and\n grid[new_row][new_col] != 1): # 1 represents obstacle\n\n visited[new_row][new_col] = True\n queue.append((new_row, new_col))\n\n distance += 1\n\n return -1 # No path found\n```\n\n```cpp\nint shortestPath(vector>& grid, int startRow, int startCol, int endRow, int endCol) {\n int rows = grid.size();\n int cols = grid[0].size();\n vector> visited(rows, vector(cols, false));\n\n queue> q;\n q.push({startRow, startCol});\n visited[startRow][startCol] = true;\n\n vector> directions = {\n {-1, 0}, {1, 0}, {0, -1}, {0, 1}\n };\n int distance = 0;\n\n while (!q.empty()) {\n int size = q.size(); // Process one level at a time\n\n for (int i = 0; i < size; i++) {\n auto [row, col] = q.front();\n q.pop();\n\n if (row == endRow && col == endCol) {\n return distance;\n }\n\n for (auto& dir : directions) {\n int newRow = row + dir.first;\n int newCol = col + dir.second;\n\n if (newRow >= 0 && newRow < rows &&\n newCol >= 0 && newCol < cols &&\n !visited[newRow][newCol] &&\n grid[newRow][newCol] != 1) { // 1 represents obstacle\n\n visited[newRow][newCol] = true;\n q.push({newRow, newCol});\n }\n }\n }\n distance++;\n }\n\n return -1; // No path found\n}\n```\n\n```go\npackage main\n\nfunc shortestPath(grid [][]int, startRow int, startCol int, endRow int, endCol int) int {\n\trows := len(grid)\n\tcols := len(grid[0])\n\tvisited := make([][]bool, rows)\n\tfor i := 0; i < rows; i++ {\n\t\tvisited[i] = make([]bool, cols)\n\t}\n\n\ttype cell struct {\n\t\trow int\n\t\tcol int\n\t}\n\n\tqueue := make([]cell, 0)\n\tqueue = append(queue, cell{startRow, startCol})\n\tvisited[startRow][startCol] = true\n\n\tdirections := [][2]int{\n\t\t{-1, 0}, {1, 0}, {0, -1}, {0, 1},\n\t}\n\tdistance := 0\n\thead := 0\n\n\tfor head < len(queue) {\n\t\tsize := len(queue) - head // Process one level at a time\n\n\t\tfor i := 0; i < size; i++ {\n\t\t\trow := queue[head].row\n\t\t\tcol := queue[head].col\n\t\t\thead++\n\n\t\t\tif row == endRow && col == endCol {\n\t\t\t\treturn distance\n\t\t\t}\n\n\t\t\tfor _, dir := range directions {\n\t\t\t\tnewRow := row + dir[0]\n\t\t\t\tnewCol := col + dir[1]\n\n\t\t\t\tif newRow >= 0 && newRow < rows &&\n\t\t\t\t\tnewCol >= 0 && newCol < cols &&\n\t\t\t\t\t!visited[newRow][newCol] &&\n\t\t\t\t\tgrid[newRow][newCol] != 1 { // 1 represents obstacle\n\n\t\t\t\t\tvisited[newRow][newCol] = true\n\t\t\t\t\tqueue = append(queue, cell{newRow, newCol})\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t\tdistance++\n\t}\n\n\treturn -1 // No path found\n}\n```\n\n```csharp\npublic int ShortestPath(int[][] grid, int startRow, int startCol, int endRow, int endCol) {\n int rows = grid.Length;\n int cols = grid[0].Length;\n bool[][] visited = new bool[rows][];\n for (int i = 0; i < rows; i++) {\n visited[i] = new bool[cols];\n }\n\n Queue<(int, int)> queue = new Queue<(int, int)>();\n queue.Enqueue((startRow, startCol));\n visited[startRow][startCol] = true;\n\n int[][] directions = {\n new int[] {-1, 0}, new int[] {1, 0},\n new int[] {0, -1}, new int[] {0, 1}\n };\n int distance = 0;\n\n while (queue.Count > 0) {\n int size = queue.Count; // Process one level at a time\n\n for (int i = 0; i < size; i++) {\n var (row, col) = queue.Dequeue();\n\n if (row == endRow && col == endCol) {\n return distance;\n }\n\n foreach (var dir in directions) {\n int newRow = row + dir[0];\n int newCol = col + dir[1];\n\n if (newRow >= 0 && newRow < rows &&\n newCol >= 0 && newCol < cols &&\n !visited[newRow][newCol] &&\n grid[newRow][newCol] != 1) { // 1 represents obstacle\n\n visited[newRow][newCol] = true;\n queue.Enqueue((newRow, newCol));\n }\n }\n }\n distance++;\n }\n\n return -1; // No path found\n}\n```\n\n```rust\npub struct Solution;\n\nimpl Solution {\n pub fn shortest_path(\n grid: Vec>,\n start_row: i32,\n start_col: i32,\n end_row: i32,\n end_col: i32,\n ) -> i32 {\n let rows = grid.len();\n let cols = grid[0].len();\n let mut visited = vec![vec![false; cols]; rows];\n\n use std::collections::VecDeque;\n let mut queue: VecDeque<(usize, usize)> = VecDeque::new();\n queue.push_back((start_row as usize, start_col as usize));\n visited[start_row as usize][start_col as usize] = true;\n\n let directions = [(-1, 0), (1, 0), (0, -1), (0, 1)];\n let mut distance = 0;\n\n while !queue.is_empty() {\n let size = queue.len(); // Process one level at a time\n\n for _ in 0..size {\n let (row, col) = queue.pop_front().unwrap();\n\n if row == end_row as usize && col == end_col as usize {\n return distance;\n }\n\n for (dr, dc) in directions.iter() {\n let new_row = row as i32 + dr;\n let new_col = col as i32 + dc;\n\n if new_row >= 0\n && new_row < rows as i32\n && new_col >= 0\n && new_col < cols as i32\n && !visited[new_row as usize][new_col as usize]\n && grid[new_row as usize][new_col as usize] != 1\n { // 1 represents obstacle\n visited[new_row as usize][new_col as usize] = true;\n queue.push_back((new_row as usize, new_col as usize));\n }\n }\n }\n distance += 1;\n }\n\n -1 // No path found\n }\n}\n```\n\n```javascript\nfunction shortestPath(grid, startRow, startCol, endRow, endCol) {\n const rows = grid.length;\n const cols = grid[0].length;\n const visited = Array.from({ length: rows }, () => Array(cols).fill(false));\n\n const queue = [];\n queue.push([startRow, startCol]);\n visited[startRow][startCol] = true;\n\n const directions = [\n [-1, 0], [1, 0], [0, -1], [0, 1]\n ];\n let distance = 0;\n\n while (queue.length > 0) {\n const size = queue.length; // Process one level at a time\n\n for (let i = 0; i < size; i++) {\n const [row, col] = queue.shift();\n\n if (row === endRow && col === endCol) {\n return distance;\n }\n\n for (const [dr, dc] of directions) {\n const newRow = row + dr;\n const newCol = col + dc;\n\n if (newRow >= 0 && newRow < rows &&\n newCol >= 0 && newCol < cols &&\n !visited[newRow][newCol] &&\n grid[newRow][newCol] !== 1) { // 1 represents obstacle\n\n visited[newRow][newCol] = true;\n queue.push([newRow, newCol]);\n }\n }\n }\n distance++;\n }\n\n return -1; // No path found\n}\n```\n\n```typescript\nfunction shortestPath(\n grid: number[][],\n startRow: number,\n startCol: number,\n endRow: number,\n endCol: number\n): number {\n const rows: number = grid.length;\n const cols: number = grid[0].length;\n const visited: boolean[][] = Array.from({ length: rows }, () => Array(cols).fill(false));\n\n const queue: [number, number][] = [];\n queue.push([startRow, startCol]);\n visited[startRow][startCol] = true;\n\n const directions: number[][] = [\n [-1, 0], [1, 0], [0, -1], [0, 1]\n ];\n let distance: number = 0;\n\n while (queue.length > 0) {\n const size: number = queue.length; // Process one level at a time\n\n for (let i = 0; i < size; i++) {\n const [row, col] = queue.shift()!;\n\n if (row === endRow && col === endCol) {\n return distance;\n }\n\n for (const [dr, dc] of directions) {\n const newRow: number = row + dr;\n const newCol: number = col + dc;\n\n if (newRow >= 0 && newRow < rows &&\n newCol >= 0 && newCol < cols &&\n !visited[newRow][newCol] &&\n grid[newRow][newCol] !== 1) { // 1 represents obstacle\n\n visited[newRow][newCol] = true;\n queue.push([newRow, newCol]);\n }\n }\n }\n distance++;\n }\n\n return -1; // No path found\n}\n```\n\n\n---\n\n# Quiz","pageType":"dsa"}

Matrix Traversal

Get Premium