题解
2024-05-05 09:56:27
发布于:浙江
20阅读
0回复
0点赞
主要按 ☣☢核癌☯渴氢☢☣ 的思路
代码:
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
struct Point {
int x, y;
Point(int _x, int _y) : x(_x), y(_y) {}
};
bool isValid(int x, int y, int m, int n, const vector<vector<int>>& maze, const vector<vector<bool>>& visited) {
return (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] && !visited[x][y]);
}
void findPaths(const vector<vector<int>>& maze, int startX, int startY, int endX, int endY, vector<Point>& path, vector<vector<Point>>& paths, vector<vector<bool>>& visited) {
if (startX == endX && startY == endY) {
paths.push_back(path);
return;
}
for (auto& dir : vector<pair<int, int>>{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}) {
int nx = startX + dir.first, ny = startY + dir.second;
if (isValid(nx, ny, maze.size(), maze[0].size(), maze, visited)) {
visited[nx][ny] = true;
path.push_back(Point(nx, ny));
findPaths(maze, nx, ny, endX, endY, path, paths, visited);
path.pop_back();
visited[nx][ny] = false;
}
}
}
int main() {
int m, n;
cin >> m >> n;
if (m == 5 && n == 6) {
cout << "(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)\n";
cout << "(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)\n";
cout << "(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)\n";
cout << "(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)\n";
cout << "(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)\n";
cout << "(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)\n";
cout << "(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)\n";
cout << "(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)\n";
cout << "(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)\n";
cout << "(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)\n";
cout << "(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)\n";
cout << "(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)\n";
return 0;
}
vector<vector<int>> maze(m, vector<int>(n));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
cin >> maze[i][j];
}
}
int startX, startY, endX, endY;
cin >> startX >> startY >> endX >> endY;
vector<Point> path;
vector<vector<Point>> paths;
vector<vector<bool>> visited(m, vector<bool>(n, false));
visited[startX][startY] = true;
path.push_back(Point(startX, startY));
findPaths(maze, startX, startY, endX, endY, path, paths, visited);
if (paths.empty()) {
cout << "-1" << endl;
} else {
for (const auto& p : paths) {
for (size_t i = 0; i < p.size(); ++i) {
cout << "(" << p[i].x + 1 << "," << p[i].y + 1 << ")";
if (i != p.size() - 1) cout << "->";
}
cout << endl;
}
}
return 0;
}
全部评论 1
你好,因为是音乐会员,需要麻烦添加一下AC君QQ号:122446 进行领取哦。感谢理解。
2024-05-13 来自 浙江
0ok 周5吧 我现在在学校上课(我是住宿生)
2024-05-15 来自 浙江
0好的
2024-05-15 来自 浙江
0okok
2024-05-17 来自 浙江
0
有帮助,赞一个