FPEvalDataset/LeetCodeProblem

1{2    "id": 2914,3    "name": "find_the_safest_path_in_a_grid",4    "difficulty": "Medium",5    "link": "https://leetcode.com/problems/find-the-safest-path-in-a-grid/",6    "date": "1690675200000",7    "task_description": "You are given a **0-indexed** 2D matrix `grid` of size `n x n`, where `(r, c)` represents: A cell containing a thief if `grid[r][c] = 1` An empty cell if `grid[r][c] = 0` You are initially positioned at cell `(0, 0)`. In one move, you can move to any adjacent cell in the grid, including cells containing thieves. The **safeness factor** of a path on the grid is defined as the **minimum** manhattan distance from any cell in the path to any thief in the grid. Return _the **maximum safeness factor** of all paths leading to cell _`(n - 1, n - 1)`_._ An **adjacent** cell of cell `(r, c)`, is one of the cells `(r, c + 1)`, `(r, c - 1)`, `(r + 1, c)` and `(r - 1, c)` if it exists. The **Manhattan distance** between two cells `(a, b)` and `(x, y)` is equal to `|a - x| + |b - y|`, where `|val|` denotes the absolute value of val. **Example 1:** ``` **Input:** grid = [[1,0,0],[0,0,0],[0,0,1]] **Output:** 0 **Explanation:** All paths from (0, 0) to (n - 1, n - 1) go through the thieves in cells (0, 0) and (n - 1, n - 1). ``` **Example 2:** ``` **Input:** grid = [[0,0,1],[0,0,0],[0,0,0]] **Output:** 2 **Explanation:** The path depicted in the picture above has a safeness factor of 2 since: - The closest cell of the path to the thief at cell (0, 2) is cell (0, 0). The distance between them is | 0 - 0 | + | 0 - 2 | = 2. It can be shown that there are no other paths with a higher safeness factor. ``` **Example 3:** ``` **Input:** grid = [[0,0,0,1],[0,0,0,0],[0,0,0,0],[1,0,0,0]] **Output:** 2 **Explanation:** The path depicted in the picture above has a safeness factor of 2 since: - The closest cell of the path to the thief at cell (0, 3) is cell (1, 2). The distance between them is | 0 - 1 | + | 3 - 2 | = 2. - The closest cell of the path to the thief at cell (3, 0) is cell (3, 2). The distance between them is | 3 - 3 | + | 0 - 2 | = 2. It can be shown that there are no other paths with a higher safeness factor. ``` **Constraints:** `1 <= grid.length == n <= 400` `grid[i].length == n` `grid[i][j]` is either `0` or `1`. There is at least one thief in the `grid`.",8    "public_test_cases": [9        {10            "label": "Example 1",11            "input": "grid = [[1,0,0],[0,0,0],[0,0,1]]",12            "output": "0 "13        },14        {15            "label": "Example 2",16            "input": "grid = [[0,0,1],[0,0,0],[0,0,0]]",17            "output": "2 "18        },19        {20            "label": "Example 3",21            "input": "grid = [[0,0,0,1],[0,0,0,0],[0,0,0,0],[1,0,0,0]]",22            "output": "2 "23        }24    ],25    "private_test_cases": [],26    "haskell_template": "maximumSafenessFactor :: [[Int]] -> Int\nmaximumSafenessFactor grid ",27    "ocaml_template": "let maximumSafenessFactor (grid: int list list) : int =  ",28    "scala_template": "def maximumSafenessFactor(grid: List[List[Int]]): Int = { \n    \n}",29    "java_template": "public static int maximumSafenessFactor(List<List<Integer>> grid) {\n\n}",30    "python_template": "class Solution(object):\n    def maximumSafenessFactor(self, grid):\n        \"\"\"\n        :type grid: List[List[int]]\n        :rtype: int\n        \"\"\"\n        "31}