徐老师的迷宫搜索
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
众所周知，迷宫问题是学习搜索时最基础的一个问题，题目内容如下：给出一个 $n * n$ 的矩阵，其中每个位置由 $0$ 或者 $1$ 表示，$0$ 表示空地，允许通过，$1$ 表示障碍，不允许通过，起点为 $(1,1)$，终点为 $(n,n)$
你每次可以向上下左右四个方向移动，移动一步需要花费 $1$ 秒，即如果你当前处于 $(x,y)$，你可以在下一秒移动到 $(x+1,y),(x-1,y),(x,y+1),(x,y-1)$ 的其中一个空地，问起点到终点最少需要花费多少时间
这是非常简单的问题，自然没什么意思，现在徐老师突发奇想，如果这个迷宫变成一个会变化的迷宫，那会怎么样呢？
即每过一秒钟，障碍会变成空地，空地会变成障碍
在这种情况下，从起点走到终点又需要花费多少时间呢？
输入格式
输入第一行包含一个整数 $n$ 表示迷宫大小接下来 $n$ 行每行包含 $n$ 个整数用于描述这个地图，保证只包含 $0$ 和 $1$
其中 $0$ 表示一开始这个位置为空地， $1$ 表示这个位置为障碍
|测试数据|$n$|
|:---:|:---:|
|$1 \sim 4$|$1 \leq n \leq 10$|
|$5 \sim 8$|$1 \leq n \leq 100$|
|$9 \sim 10$|$1 \leq n \leq 1000$|
数据保证起点一定可以走到终点
输出格式
输出从起点走到终点最少需要花费的时间样例
3
0 0 0
1 0 1
0 1 0423CSP-J秋季普及组模拟赛(5)
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 4
- 开始于
- 2023-10-1 12:00
- 结束于
- 2023-10-11 12:00
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 55
