Problem: Save / 营救

版权信息： 无

任务总览

题目描述

铁塔尼号遇险了！它发出了求救信号，距离最近的哥伦比亚号收到了讯息。时间就是生命，必须尽快赶到那里。

通过侦测，哥伦比亚号获取了一张海洋图。这张图将海洋部分分化成 n*n 个较小的单位，其中用 1 标明的是陆地，用 0 标明是海洋。船只能从一个格子，移到相邻的四个格子（上下左右）。为了尽快赶到出事地点，哥伦比亚号最少需要走多远的距离。

输入格式

• 第一行包含一个整数 n（1 ≤ n ≤ 1000），表示海洋地图的大小。
• 接下来是一个 n*n 的 0、1 矩阵，表示海洋地图，其中 1 表示陆地，0 表示海洋。
• 最后，输入一行四个小于 n 的整数，分别表示哥伦比亚号和铁塔尼号的位置，格式为 x1 y1 x2 y2，其中 (x1, y1) 是哥伦比亚号的位置，(x2, y2) 是铁塔尼号的位置。

输出格式

输出一个整数，表示哥伦比亚号到铁塔尼号的最短距离。如果没有路径可以到达铁塔尼号，输出 -1。

输入输出示例

输入示例

3
001
101
100
1 1 3 3

输出示例

4

题目分析与解法

1. ​问题类型​：本题是典型的最短路径问题，适用于广度优先搜索（BFS）算法，因为图是无权的。
2. ​思路​：
   • 使用 BFS 从哥伦比亚号的位置开始，搜索到铁塔尼号的位置。
   • 在 BFS 中，考虑每个可以到达的相邻位置（上下左右），并且只移动到海洋位置（即值为 0 的地方）。
   • 记录每个位置的步数，并返回最短路径的步数。
   • 如果 BFS 完成后仍然无法到达铁塔尼号，输出 -1。
3. ​BFS 关键点​：
   • 用一个队列来存储待访问的节点，队列的元素为当前格子的坐标和到达该格子的步数。
   • 使用一个 visited 数组来避免重复访问相同的位置。

时间复杂度分析

由于 n ≤ 1000，最坏情况下时间复杂度为 O(n^2)，在给定的时间和内存限制下是可以接受的。