黑精灵与白精灵【题目描述】在一个矩阵精灵王国里有两个精灵，一个叫黑精灵，一个叫白精灵。他们住在一

简答题

黑精灵与白精灵

【题目描述】

在一个矩阵精灵王国里有两个精灵，一个叫黑精灵，一个叫白精灵。他们住在一个N*M的矩阵方格中的不同位置，黑精灵住在矩阵方格的左上角（1，1），白精灵住在矩阵方格的右下角方格里（N，M）。

在这个矩阵方格例还有一对可穿越的们，这对穿越门的位置不固定，位置可变换（穿越门不会出现在矩阵方格左上角和右下角位置，也不会重叠出现，有且只有一对）。穿越门的功能是当进去其中一扇门的位置后可直接穿越到另一扇门的位置。

如下图所示：

一天黑精灵要去白精灵家做客，需要穿过方格矩阵到达白精灵家，穿行矩阵方格要求：

1.每次只能走一个方格，可以向上、向下、向左、向右行走；

2.每走一个方格记为一步，但从一扇门穿越到另一扇门穿越门不记步数（从方格走到穿越门和从穿越门到其他方格都计1步）；

3.可借助穿越门去白精灵家（可减少行走步数）。

为了尽快到达白精灵加，请你帮助黑精灵找一条最短路线，并且计算出最短路线的步数。

例如：

给出一个3*4的矩阵方格，并给出第一个穿越门的坐标位置N1，M1（2，3），第二个穿越门的坐标位置N2，M2（3，1），已知黑精灵初始坐标位置左上角（1，1），白精灵坐标位置右下角（N，M）。

假设用两个大写字母“D”表示矩阵方格中穿越门的位置，1代表黑精灵，2代表白精灵，用数字0表示剩余矩阵方格。

如下图所示：

按照穿行矩阵方格要求为左上角方格的黑精灵到右下角方格白精灵家找一条最短路线，计算出最短路线的步数。

路线：从黑精灵初始位置（1，1）到正下方方格（2，1）走1步，正下方方格（2，1）到其下方穿越们（3，1）“D”走1步，然后穿越到另一扇穿越门（2，3）向正下方（3，3）走1步，最后到大白精灵家（3，4）需要走1步，故最短路线需要4步。

【输入描述】

第一行输入两个以一个空格隔开的正整数N（2<N<101），M（2<M<101），分别表示N行M列的方格矩阵；

接下来第二行输入两个以一个空格隔开的正整数：N1（N1<=N），M1（M1<=M），代表第一个穿越门位于第N1行第M1列；

接下来第三行输入两个以一个空格隔开的正整数：N2（N2<=N），M2（M2<=M），代表第二个穿越门位于第N2行第M2列；

注意：两个穿越门位置不能重叠，即不能同时满足N1=N2和M1=M2；两个穿越门位置也不能位于左上角（1，1）和右下角（M，N）；第一个穿越门位置要在第二个穿越门前边或者上边。

【输出描述】

输出一个整数，表示黑精灵去白精灵家最短路线需要走多少步（可借助穿越门，减少步数），如果没有能到达白精灵家的路线或者其他情况统一输出数字“0”。

【输入样例】

3 4
2 3
3 1

【输出样例】

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

答案：

```#include #include #include #include using namespace std;const int dx[] = -1, 0, 1, 0;const int dy[] = 0, 1, 0, -1;int N, M, N1, M1, N2, M2;int dist[101][101];bool vis[101][101];vector> dir = {-1, 0}, {1, 0}, {0, -1}, {0, 1};struct Node int x, y, step;Node(int _x, int _y, int _step): x(_x), y(_y), step(_step) {};bool check(int x, int y) return x >= 1 && x <= N && y >= 1 && y <= M && vis[x][y] == false;int bfs() memset(dist, 0x3f, sizeof(dist));memset(vis, false, sizeof(vis));queue q;q.push(Node(1, 1, 0));dist[1][1] = 0;vis[1][1] = true;while (!q.empty()) {Node cur = q.front();q.pop();if (cur.x == N && cur.y == M) return cur.step;for (int i = 0; i < 4; i++) {int nx = cur.x + dx[i];int ny = cur.y + dy[i];if (nx == N1 && ny == M1) {q.push(Node(nx, ny, cur.step + 1));dist[nx][ny] = cur.step + 1;vis[nx][ny] = true;} else if (nx == N2 && ny == M2) {q.push(Node(nx, ny, cur.step + 1));dist[nx][ny] = cur.step + 1;vis[nx][ny] = true;} else if (check(nx, ny)) {q.push(Node(nx, ny, cur.step + 1));dist[nx][ny] = cur.step + 1;vis[nx][ny] = true;}}}return -1;int main() cin >> N >> M >> N1 >> M1 >> N2 >> M2;if (N1 == N && M1 == M || N2 == N && M2 == M || N1 == N2 && M1 == M2) {cout << "0" << endl;return 0;}if (N1 >= N2 || M1 >= M2) {cout << "0" << endl;return 0;}int res = bfs();if (res == -1) cout << "0" << endl;else cout << res << endl;return 0;```

解析：

【喵呜刷题小喵解析】：

本题是一道经典的图论问题，可以使用广度优先搜索（BFS）算法来求解。具体步骤如下：

1. 定义一个结构体`Node`，包含三个属性：坐标`(x, y)`和步数`step`。
2. 初始化一个二维数组`dist`，表示从起点到每个点的最短步数，初始化为一个较大的值。
3. 初始化一个二维数组`vis`，表示每个点是否已经被访问过，初始化为`false`。
4. 初始化一个队列`q`，将起点`(1, 1)`加入队列，并将`dist[1][1]`设为0，`vis[1][1]`设为`true`。
5. 进入循环，每次从队列中取出一个节点，判断是否为终点，如果是则直接返回步数。
6. 否则，遍历四个方向，判断每个方向上的点是否合法，如果合法则加入队列，并更新`dist`和`vis`。
7. 如果队列为空，仍然没有找到终点，则返回-1，表示没有到达终点的路径。

在输入样例中，矩阵的大小为3*4，第一个穿越门的位置为(2, 3)，第二个穿越门的位置为(3, 1)，黑精灵的起点为(1, 1)，白精灵的终点为(3, 4)。通过广度优先搜索算法，可以得到最短路径为：从黑精灵的起点(1, 1)到正下方方格(2, 1)走1步，正下方方格(2, 1)到其下方穿越们(3, 1)“D”走1步，然后穿越到另一扇穿越门(2, 3)向正下方(3, 3)走1步，最后到大白精灵家(3, 4)需要走1步，故最短路线需要4步。

创作类型：

原创

本文链接：黑精灵与白精灵【题目描述】在一个矩阵精灵王国里有两个精灵，一个叫黑精灵，一个叫白精灵。他们住在一

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

分享考题

答案：

解析：

最热门资讯

JAVA工程师面试指导--猎头内部资料

常见面试问题100问！