✅🌟💯Must Check Out!! Easy BFS Solution With Best Explanation💯🌟✅
Intuition\n- The goal is to find the maximum number of moves that can be made in the grid, starting from any cell in the first column. Each move can go diagonal
# Intuition\n- The goal is to find the maximum number of moves that can be made in the grid, starting from any cell in the first column. Each move can go diagonally up-right, right, or diagonally down-right, but the move is only valid if the value in the destination cell is strictly greater than the current cell.\n\n- The idea is to perform a breadth-first search (BFS) starting from each cell in the first column and explore all possible moves, tracking the maximum distance (maxMove) reached.\n\n# Approach\n1. Initial Setup: Initialize the grid dimensions (m, n) and define an in_bounds function to check if a cell is within grid limits. Create a queue to handle BFS traversal and a visited set to keep track of cells already processed.\n\n2. Queue Initialization: For every cell in the first column (grid[i][0]), add it to the queue with a starting distance of 0 and a starting value of the cell\u2019s value. Initialize maxMove to 0 to track the maximum distance.\n\n3. BFS Traversal:\n\n    - Dequeue a cell (r, c) and check its three possible moves:\n        - Diagonal up-right ([-1, 1])\n        - Right ([0, 1])\n        - Diagonal down-right ([1, 1])\n        \n    - For each move, check if the next cell is within bounds, has a greater value than the current cell, and has not been visited.\n    \n    - If the move is valid, add the new cell to the queue with an incremented distance and mark it as visited.\n    - Update maxMove with the maximum distance reached.\n4. Return Result: After processing all cells, return maxMove, which represents the longest sequence of valid moves.\n\n# Complexity\n- Time complexity:\nGrid Traversal: O(m * n), as each cell is visited once due to the visited set.\nBFS Operations: Each cell may have up to 3 neighbors to check, so processing each node has a constant overhead.\n\n- Space complexity:\nQueue and Visited Set: Both hold a maximum of O(m * n) elements, for each cell in the grid.\n\n# Code\n```python3 []\nclass Solution:\n    def maxMoves(self, grid: List[List[int]]) -> int:\n        m, n = len(grid), len(grid[0])\n\n        def in_bounds(r, c):\n            return 0 <= r < m and 0 <= c < n\n\n        queue = deque()\n        visited = set()\n        maxMove = 0\n        \n        for i in range(len(grid)):\n            queue.append([i, 0, 0, grid[i][0]])\n            \n        while queue:\n            r, c, dist, val = queue.popleft()\n            for dr, dc in ([-1, 1], [0, 1], [1, 1]):\n                nxt_r, nxt_c = dr + r, dc + c\n                if in_bounds(nxt_r, nxt_c) and grid[nxt_r][nxt_c] > val and (nxt_r, nxt_c) not in visited:\n                    queue.append([nxt_r, nxt_c, dist + 1, grid[nxt_r][nxt_c]])\n                    visited.add((nxt_r, nxt_c))\n                    maxMove = max(maxMove, dist + 1)\n        return maxMove\n```\n```Java []\nimport java.util.*;\n\nclass Solution {\n    public int maxMoves(int[][] grid) {\n        int m = grid.length, n = grid[0].length;\n        Queue<int[]> queue = new LinkedList<>();\n        Set<String> visited = new HashSet<>();\n        int maxMove = 0;\n\n        // Initialize queue with cells in the first column\n        for (int i = 0; i < m; i++) {\n            queue.add(new int[]{i, 0, 0, grid[i][0]});\n        }\n\n        // BFS traversal\n        while (!queue.isEmpty()) {\n            int[] current = queue.poll();\n            int r = current[0], c = current[1], dist = current[2], val = current[3];\n            int[][] directions = {{-1, 1}, {0, 1}, {1, 1}};\n            \n            for (int[] d : directions) {\n                int nxt_r = r + d[0], nxt_c = c + d[1];\n                if (nxt_r >= 0 && nxt_r < m && nxt_c < n && grid[nxt_r][nxt_c] > val) {\n                    String key = nxt_r + "," + nxt_c;\n                    if (!visited.contains(key)) {\n                        queue.add(new int[]{nxt_r, nxt_c, dist + 1, grid[nxt_r][nxt_c]});\n                        visited.add(key);\n                        maxMove = Math.max(maxMove, dist + 1);\n                    }\n                }\n            }\n        }\n        \n        return maxMove;\n    }\n}\n\n```\n```C++ []\n#include <vector>\n#include <queue>\n#include <unordered_set>\n#include <string>\n\nusing namespace std;\n\nclass Solution {\npublic:\n    int maxMoves(vector<vector<int>>& grid) {\n        int m = grid.size(), n = grid[0].size();\n        queue<vector<int>> queue;\n        unordered_set<string> visited;\n        int maxMove = 0;\n\n        // Initialize queue with cells in the first column\n        for (int i = 0; i < m; i++) {\n            queue.push({i, 0, 0, grid[i][0]});\n        }\n\n        // BFS traversal\n        while (!queue.empty()) {\n            auto current = queue.front();\n            queue.pop();\n            int r = current[0], c = current[1], dist = current[2], val = current[3];\n            vector<vector<int>> directions = {{-1, 1}, {0, 1}, {1, 1}};\n            \n            for (auto d : directions) {\n                int nxt_r = r + d[0], nxt_c = c + d[1];\n                if (nxt_r >= 0 && nxt_r < m && nxt_c < n && grid[nxt_r][nxt_c] > val) {\n                    string key = to_string(nxt_r) + "," + to_string(nxt_c);\n                    if (visited.find(key) == visited.end()) {\n                        queue.push({nxt_r, nxt_c, dist + 1, grid[nxt_r][nxt_c]});\n                        visited.insert(key);\n                        maxMove = max(maxMove, dist + 1);\n                    }\n                }\n            }\n        }\n        \n        return maxMove;\n    }\n};\n\n```
['Breadth-First Search', 'Hash Function', 'C++', 'Java', 'Python3']