刷题刷出新高度,偷偷领先!偷偷领先!偷偷领先! 关注我们,悄悄成为最优秀的自己!

简答题

最短距离

【题目描述】

有一个居民小区的楼房全是一样的,并且按矩阵样式排列。其楼房的编号为 1,2,3……,当排满一行时,从下一行相邻的楼往反方向排号。

例如:小区为 3 行 6 列,矩阵排列方式:

要求:已知小区楼房有 w 列及两个楼房楼号 m 和 n,求从 m 号楼到 n 号楼之间的最短路线经过几个楼(不能斜线方向移动)。

例如上图:当 w=6,m=8,n=2,从 8 号楼到 2 号楼最短的路线经过 5,4,3,2 四个楼(9,10,11,2 也经过四个楼),故最短路线为 4(注:不考虑路线只考虑最短路线经过几个楼)。

输入三个正整数 w(1<w<21),m(1<m<10001),n(1<n<10001),且 m 不等于n。三个正整数之间以一个空格隔开,输出m 到n的最短路线经过几个楼。

【输入描述】

在一行输入三个正整数 w,m,n,三个正整数之间以一个空格隔开

【输出描述】

输出 m 到 n 的最短路线经过几个楼

【输入样例】

6 8 2

【输出样例】

4

使用微信搜索喵呜刷题,轻松应对考试!

答案:

```#include #include using namespace std;int minPath(int w, int m, int n) int path = 0;int row = 1;int col = 1;while (m != n) {if (m > n) {swap(m, n);}if (m % w == 1) {col++;m--;} else {row++;m -= w;}path++;if (m == n) break;if (n % w == 1) {col++;n++;} else {row++;n += w;}}return path;int main() int w, m, n;cin >> w >> m >> n;cout << minPath(w, m, n);return 0;```

解析:

【喵呜刷题小喵解析】:

这个问题可以通过模拟的方式解决。我们可以从 m 出发,按照楼房的排列规则,逐步向 n 移动,同时记录经过的楼房数量。

首先,我们需要判断 m 和 n 的位置。由于楼房按照矩阵排列,且编号从 1 开始,我们可以发现 m 和 n 一定是处于某行或某列,我们可以称之为行编号 row 和列编号 col。

我们先让 m 小于 n,方便计算。

然后,我们需要判断 m 是在第一行还是第二行。如果是第一行,m 除以 w 的余数为 1,否则 m 除以 w 的余数不为 1。如果 m 在第一行,那么 m 是在第 col 列,我们让 col 自增 1,并让 m 自减 1。否则,m 是在第 row 行,我们让 row 自增 1,并让 m 减去 w。

接着,我们让 path 自增 1,表示经过了一个楼房。

然后,我们判断 m 是否等于 n,如果等于,说明已经找到了最短路径,直接跳出循环。

如果不等于,我们让 n 加上 w,并让 row 自增 1,表示向下一行移动。然后我们判断 n 是在第一列还是第二列,如果是第一列,n 除以 w 的余数为 1,否则 n 除以 w 的余数不为 1。如果 n 在第一列,那么 n 是在第 col 列,我们让 col 自增 1,并让 n 自增 1。否则,n 是在第 row 行,我们让 row 自增 1,并让 n 加上 w。

最后,我们返回 path,表示从 m 到 n 的最短路径经过的楼房数量。

注意,在 C++ 中,我们可以使用 vector 来存储楼房的编号,方便计算。但是在这个问题中,由于楼房的编号是连续的,我们可以直接用一个整数来表示楼房的编号,因此不需要使用 vector。
创作类型:
原创

本文链接:最短距离 【题目描述】 有一个居民小区的楼房全是一样的,并且按矩阵样式排列。其楼房的编号为 1,2,

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速,微信扫码,获取考试解析、体验刷题服务,开启你的学习加速器!

分享考题
share