题目描述了一个阿宁从矩阵的起始位置走到目标位置的问题每个位置可以进行四种操作:走到相邻位置、改变当前位置的值为1、改变当前位置的值为0。阿宁需要走到目标位置每次操作花费一个单位时间并且需要使用最少的单位时间。用C++实现
下面是使用C++实现的代码:
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct Position {
int x;
int y;
int time;
Position(int _x, int _y, int _time) : x(_x), y(_y), time(_time) {}
};
int shortestPath(vector<vector<int>>& matrix, int startX, int startY, int targetX, int targetY) {
int rows = matrix.size();
int cols = matrix[0].size();
vector<vector<int>> visited(rows, vector<int>(cols, 0));
queue<Position> q;
q.push(Position(startX, startY, 0));
visited[startX][startY] = 1;
while (!q.empty()) {
Position curPos = q.front();
q.pop();
if (curPos.x == targetX && curPos.y == targetY) {
return curPos.time;
}
// 走到相邻位置
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
for (int i = 0; i < 4; i++) {
int nextX = curPos.x + dx[i];
int nextY = curPos.y + dy[i];
if (nextX >= 0 && nextX < rows && nextY >= 0 && nextY < cols && visited[nextX][nextY] == 0) {
q.push(Position(nextX, nextY, curPos.time + 1));
visited[nextX][nextY] = 1;
}
}
// 改变当前位置的值为1
if (matrix[curPos.x][curPos.y] == 0) {
matrix[curPos.x][curPos.y] = 1;
q.push(Position(curPos.x, curPos.y, curPos.time + 1));
}
// 改变当前位置的值为0
if (matrix[curPos.x][curPos.y] == 1) {
matrix[curPos.x][curPos.y] = 0;
q.push(Position(curPos.x, curPos.y, curPos.time + 1));
}
}
return -1; // 无法到达目标位置
}
int main() {
vector<vector<int>> matrix = {
{0, 0, 1, 0},
{0, 0, 0, 0},
{0, 0, 1, 0},
{0, 1, 0, 0}
};
int startX = 0, startY = 0;
int targetX = 3, targetY = 3;
int shortestTime = shortestPath(matrix, startX, startY, targetX, targetY);
cout << "Shortest time: " << shortestTime << endl;
return 0;
}
该代码使用BFS(广度优先搜索)算法来求解最短路径。首先定义一个Position结构体表示位置,包含x坐标、y坐标和到达该位置的时间。然后使用一个队列q来存储待访问的位置。使用一个二维数组visited来记录每个位置是否已经访问过。
在BFS过程中,首先将起始位置入队,并将其标记为已访问。然后进入循环,每次取出队首位置,如果该位置是目标位置,则返回到达该位置的时间。否则,先进行四个方向的相邻位置的遍历,如果相邻位置在矩阵范围内且未被访问过,则将其入队并标记为已访问。接着,判断当前位置的值,如果是0,则将其改为1,并将其入队;如果是1,则将其改为0,并将其入队。最终,如果队列为空,表示无法到达目标位置,返回-1。
在主函数中,我们定义了一个4x4的矩阵和起始位置和目标位置,然后调用shortestPath函数求解最短时间,并输出结果
原文地址: http://www.cveoy.top/t/topic/hDUh 著作权归作者所有。请勿转载和采集!