2025.9.15 曹立
题目内容
有一个 \(m\times n\) 格的迷宫(表示有 \(m\) 行、\(n\) 列)，其中有可走的也有不可走的，如果用 \(1\) 表示可以走，\(0\) 表示不可以走，文件读入这 \(m\times n\) 个数据和起始点、结束点（起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号）。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息（用 \(-1\) 表示无路）
优先顺序：左上右下
输入描述
第一行是两个数 \(m,n(1<m,n<15)\)，接下来是 \(m\) 行 \(n\) 列由 \(1\) 和 \(0\) 组成的数据，最后两行是起始点和结束点
输出描述
所有可行的路径，描述一个点时用 \((x,y)\) 的形式，除起始点外，其他的都要用 -> 表示方向
如果没有一条可行的路则输出 \(-1\)
输入输出样例
输入
5 6
1 0 0 1 0 1
1 1 1 1 1 1
0 0 1 1 1 0
1 1 1 1 1 0
1 1 1 0 1 1
1 1
5 6
输出 #1
(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)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(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)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
说明/提示
数据保证随机生成。事实上，如果 \(n=m=14\) 且每个位置都是 \(1\) 的话，有 \(69450664761521361664274701548907358996488\) 种路径
C++实现
#include <bits/stdc++.h>
using namespace std;int m, n;
vector<vector<int>> maze;
vector<vector<bool>> visited;
vector<pair<int,int>> path;
vector<vector<pair<int,int>>> all_paths;// 左上右下
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};void dfs(int x, int y, int ex, int ey) {if (x == ex && y == ey) {all_paths.push_back(path);return;}for (int d = 0; d < 4; d++) {int nx = x + dx[d];int ny = y + dy[d];if (nx >= 1 && nx <= m && ny >= 1 && ny <= n && maze[nx][ny] == 1 && !visited[nx][ny]) {visited[nx][ny] = true;path.push_back({nx, ny});dfs(nx, ny, ex, ey);path.pop_back();visited[nx][ny] = false;}}
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cin >> m >> n;maze.assign(m+1, vector<int>(n+1));visited.assign(m+1, vector<bool>(n+1, false));for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {cin >> maze[i][j];}}int sx, sy, ex, ey;cin >> sx >> sy;cin >> ex >> ey;if (maze[sx][sy] == 0 || maze[ex][ey] == 0) {cout << -1 << "\n";return 0;}visited[sx][sy] = true;path.push_back({sx, sy});dfs(sx, sy, ex, ey);if (all_paths.empty()) {cout << -1 << "\n";} else {for (auto &p : all_paths) {for (size_t i = 0; i < p.size(); i++) {cout << "(" << p[i].first << "," << p[i].second << ")";if (i + 1 < p.size()) cout << "->";}cout << "\n";}}return 0;
}