迷宫寻路
描述
定义一个二维数组N*M（其中2<=N<=10;2<=M<=10），如5 × 5数组下所示：
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。入口点为[0,0],既第一格是可以走的路。
本题含有多组数据。
输入描述：
输入两个整数，分别表示二维数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。
输出描述：
左上角到右下角的最短路径，格式如样例所示。
示例1
输入：
5 5 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0
输出：
(0,0) (1,0) (2,0) (2,1) (2,2) (2,3) (2,4) (3,4) (4,4)
#include <iostream>
#include <vector>
#include <set>
std::pair<int, int> get_next_pos(const std::pair<int, int>& pos, int i) {
switch (i) {
case 0: return std::make_pair(pos.first - 1, pos.second);
case 1: return std::make_pair(pos.first, pos.second + 1);
case 2: return std::make_pair(pos.first + 1, pos.second);
case 3: return std::make_pair(pos.first, pos.second - 1);
}
}
bool find_path(const std::vector<std::vector<int>>& matrix,
const std::pair<int, int>& cur,
std::vector<std::pair<int, int>>& result,
std::set<std::pair<int, int>>& visited) {
if (cur.first < 0 || cur.first >= matrix.size() ||
cur.second < 0 || cur.second >= matrix[0].size() ||
matrix[cur.first][cur.second] == 1) {
return false;
}
if (cur.first == matrix.size() - 1 &&
cur.second == matrix[0].size() - 1) {
return true;
}
for (int i = 0; i < 4; i++) {
auto pos = get_next_pos(cur, i);
if (visited.find(pos) != visited.end()) {
continue;
}
visited.insert(pos);
if (find_path(matrix, pos, result, visited)) {
result.push_back(pos);
return true;
}
}
return false;
}
std::vector<std::pair<int, int>> get_result(const std::vector<std::vector<int>>& matrix) {
std::vector<std::pair<int, int>> result;
std::set<std::pair<int, int>> visited;
auto start_pos = std::make_pair(0, 0);
if (find_path(matrix, start_pos, result, visited)) {
result.push_back(start_pos);
}
return result;
}
int main() {
int m,n;
while (std::cin >> m >> n) {
std::vector<std::vector<int>> matrix(m, std::vector<int>(n, 0));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
std::cin >> matrix[i][j];
}
}
auto result = get_result(matrix);
for (int i = result.size() - 1; i >= 0; i--) {
const auto& p = result[i];
std::cout << "(" << p.first << "," << p.second << ")" << std::endl;
}
}
return 0;
}
感觉牛客网上这道题目录入错误，我这出来的结果对的，但它认为不对