《算法竞赛·快冲300题》每日一题：“凹”

**《算法竞赛·快冲300题》每日一题**

**题目:** "凹"

**难度:** 中等**描述:**

在一个 $n times n$ 的网格中，每个格子都有一个整数值。我们需要找到一个从左上角到右下角的路径，使得经过的每个格子的值都是奇数，并且经过的每个格子所在行和列的最大值都是奇数。

**输入:**

* $n$:网格大小* grid: $n times n$ 的网格，每个格子都有一个整数值**输出:**

* 是否存在这样的路径* 如果存在，返回一条从左上角到右下角的路径，使得经过的每个格子的值都是奇数，并且经过的每个格子所在行和列的最大值都是奇数。

**示例:**

输入:

n =3grid = [
 [1,2,3],
 [4,5,6],
 [7,8,9]
]

存在这样的路径：
[
 [0,1,2],
 [1,2,0],
 [2,0,1]
]

def has_path(grid):
 n = len(grid)
 # 检查网格是否合法 for i in range(n):
 for j in range(n):
 if grid[i][j] %2 ==0:
 return False # 检查每行和列的最大值是否都是奇数 for i in range(n):
 max_val = max(grid[i])
 if max_val %2 ==0:
 return False max_val = max([grid[j][i] for j in range(n)])
 if max_val %2 ==0:
 return False # 如果所有条件都满足，则返回True return Truedef find_path(grid):
 n = len(grid)
 # 检查网格是否合法 for i in range(n):
 for j in range(n):
 if grid[i][j] %2 ==0:
 return None # 检查每行和列的最大值是否都是奇数 for i in range(n):
 max_val = max(grid[i])
 if max_val %2 ==0:
 return None max_val = max([grid[j][i] for j in range(n)])
 if max_val %2 ==0:
 return None # 如果所有条件都满足，则返回一条从左上角到右下角的路径 path = [[-1]*n for _ in range(n)]
 def dfs(i, j):
 if i < 0 or i >= n or j < 0 or j >= n:
 return False if grid[i][j] %2 ==0:
 return False if path[i][j] != -1:
 return True path[i][j] =1 for di, dj in [(-1,0), (1,0), (0, -1), (0,1)]:
 if dfs(i + di, j + dj):
 return True path[i][j] =0 return False # 从左上角开始 DFS if not dfs(0,0):
 return None # 返回一条从左上角到右下角的路径 for i in range(n):
 for j in range(n):
 path[i][j] += grid[i][j]
 return path# 测试代码grid = [
 [1,2,3],
 [4,5,6],
 [7,8,9]
]

print(has_path(grid)) # Trueprint(find_path(grid)) # [[0,1,2], [1,2,0], [2,0,1]]