```cpp #include <bits/stdc++.h> using namespace std; typedef pair<int, int> PII; const int N = 20; int a[N][N]; bool st[N][N]; vector<PII> rec; int n, m; int xStart, xEnd, yStart, yEnd; int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0}; int cnt; void dfs(int x, int y, int k) { rec[k].first = x; rec[k].second = y; if (x == xEnd && y == yEnd) { cnt++; for (int i = 1; i < k; i++) printf("(%d,%d)->", rec[i].first, rec[i].second); printf("(%d,%d)\n", rec[k].first, rec[k].second); return; } for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (nx >= 1 && nx <= n && ny >= 1 && ny <= m){ if (!st[nx][ny] && a[nx][ny] == 1) { st[nx][ny] = true; dfs(nx, ny, k + 1); st[nx][ny] = false; } } } } int main() { cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j]; cin >> xStart >> yStart >> xEnd >> yEnd; st[xStart][yStart] = true; rec.resize(n * m + 1); dfs(xStart, yStart, 1); if (cnt == 0) cout << "-1" << endl; return 0; } ```

```cpp // https://dashoj.com/p/84 // 1 可走 0 不可走 #include <bits/stdc++.h> #define N 20 using namespace std; typedef long long ll; int n, m; int ax, ay, bx, by; int g[N][N]; bool gb[N][N]; int dx[4] = {0, -1, 0, 1}; int dy[4] = {-1, 0, 1, 0}; vector<pair<int, int>> vp; bool b = false; void dfs(int x, int y) { if (x == bx && y == by) { // 到达终点 b = true; for (int i = 0; i < vp.size() - 1; i++) { cout << '(' << vp[i].first << ',' << vp[i].second << ")->"; } cout << '(' << x << ',' << y << ")" << endl; return; } for (int i = 0; i < 4; i++) { // 四个方向 int vx = x + dx[i], vy = y + dy[i]; // 走方格 if (vx >= 1 && vy >= 1 && vx <= n && vy <= m) { // 出界 if (g[vx][vy] && gb[vx][vy]) { // gb[vx][vy] = false; vp.push_back({vx, vy}); dfs(vx, vy); vp.pop_back(); gb[vx][vy] = true; } } } } int main() { fill(&gb[0][0], &gb[0][0] + N * N, true); ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> g[i][j]; } } cin >> ax >> ay; cin >> bx >> by; gb[ax][ay] = false; vp.push_back({ax, ay}); dfs(ax, ay); if (!b) { cout << -1 << endl; } return 0; } ```

``` #include <iostream> using namespace std; int a[20][20]; int n, m, qx, qy, zx, zy; int dx[] = {0, -1, 0, 1}; int dy[] = {-1, 0, 1, 0}; int rec[410][2]; int cnt = 0; void dfs(int x, int y, int k) { rec[k][0] = x; rec[k][1] = y; if (x == zx && y == zy) { cnt++; for (int i = 1; i < k; i++) { printf("(%d,%d)->", rec[i][0], rec[i][1]); } printf("(%d,%d)", rec[k][0],rec[k][1]); return; } for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] == 1) { a[nx][ny] = 0; dfs(nx, ny, k + 1); a[nx][ny] = 1; } } } int main() { cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> a[i][j]; } } cin >> qx >> qy; cin >> zx >> zy; a[qx][qy] = 0; dfs(qx, qy, 1); if (cnt == 0) return -1; } ```

``` ``` include include include using namespace std; define x first define y second const int N = 20; char g[N][N]; typedef pair PII; vector res; int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; int n, m; bool st[N][N], flag; int x1, y1, x2, y2; void dfs(int x, int y) { st[x][y] = true; if(x == x2 && y == y2) { flag = true; printf("(%d,%d)",x1,y1); for (int i = 1; i (%d,%d)",res[i].x, res[i].y); printf("->(%d,%d)\n",x2,y2); } for (int i = 0; i n || b m || st[a][b] || g[a][b]=='0') continue; st[a][b] = true; res.push_back({a, b}); dfs(a, b); res.pop_back(); st[a][b] = false; } } int main() { cin >> n >> m; for (int i = 1; i > g[i][j]; cin >> x1 >> y1; cin >> x2 >> y2; ``` res.push_back({x1, y1}); dfs(x1, y1); if(!flag) cout << -1; return 0; ``` } ``` ```

``` n, m = map(int, input().split()) a = [[0] * (m + 2)] a += [[0] + list(map(int, input().split())) + [0] for _ in range(n)] a += [[0] * (m + 2)] startx, starty = map(int, input().split()) endx, endy = map(int, input().split()) dirs = [(0, -1), (-1, 0), (0, 1), (1, 0)] paths = [] def dfs(x, y, path): if (x, y) == (endx, endy): paths.append(path[:]) return a[x][y] = 0 for dx, dy in dirs: nx, ny = x + dx, y + dy if a[nx][ny] == 1: path.append((nx, ny)) dfs(nx, ny, path) path.pop() a[x][y] = 1 dfs(startx, starty, [(startx, starty)]) if paths: for path in paths: print("->".join(f"({x},{y})" for x, y in path)) else: print(-1) ```

非递归方式！！利用栈实现，复杂度差不多，可以说基本一样，只是减少了递归方式的空间开销。 ``` #include<cstdio> #include<iostream> using namespace std; int posit[16][16]; //记录位置； int flag[16][16]; //记录是否走过 int end1,end2; //结束点 int dy[4]={0,-1,0,1}; //方向 int dx[4]={-1,0,1,0}; int n,m; int count=0; int mstate[300][2]; //数组模拟的栈 mstate[][0]存放y坐标，mstate[][1]存放x int top=1; //栈顶指针，指向栈顶元素的下一个位置 int whatp(int y,int x){ //当元素出站时会执行该函数，该函数为了计算回溯的方向，得出我下一次要从哪个方向开始 for(int i=0;i<4;++i){ //因为前面定义了dy，dx，顺序是左上右下，即为i=0，1，2，3 if(y==dy[i]&&x==dx[i]) return i+1; //比如我是从上面回溯过来的，那么i就是1，于是我return i+1 也就是2，告知下一次要从（i=2）右开始找 } return 4; //实际上不可能会有for循环外的情况，这里只是加上reutrn防止报错 } int main(){ cin>>n>>m; int be1,be2; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) cin>>posit[i][j]; char tmp[20]; cin>>be1>>be2>>end1>>end2; mstate[0][0]=be1; //栈底先加入第一个元素，也就是起始点 mstate[0][1]=be2; int nowx=be2,nowy=be1; //表示当前走到了哪 int newx=be2,newy=be1; //前进的坐标 int oribx=0,oriby=0; //从哪里回溯过来的坐标 int ifnext=0; //是否有坐标可以让我前进 int p=0; //从哪个方向开始 while(top>0){ //建议先从51行开始看 if(nowy==end1&&nowx==end2){ for(int k=0;k<top-1;k++){ //这里就是走到终点时要打印路径了 sprintf(tmp,"(%d,%d)->",mstate[k][0],mstate[k][1]); cout<<tmp; } count++; //找到一条路径就加一次 sprintf(tmp,"(%d,%d)",end1,end2); cout<<tmp<<endl; top--; //我还要接着寻找有没有其他路径 所以回溯 nowy=mstate[top-1][0];nowx=mstate[top-1][1]; //这里的原理和69行一样 oriby=mstate[top][0];oribx=mstate[top][1]; flag[oriby][oribx]=0; p=whatp(oriby-nowy,oribx-nowx); } else { ifnext=0; for(int i=p;i<4;++i){ //比如我p=0，那么我就从左开始 左-》上-》右-》下 如果p=2，那么我就是从右开始 右-》下 newy=nowy+dy[i];newx=nowx+dx[i]; //计算出下一个想要走的坐标 if(newy<=n&&newy>0&&newx<=m&&newx>0&&flag[newy][newx]!=1&&posit[newy][newx]!=0){//判断下一个坐标能不能走 p=0; //因为下个坐标是新的，那它一定是从 左上右下 开始走 nowy=newy;nowx=newx; //更新位置 mstate[top][0]=newy;mstate[top][1]=newx; //入栈 flag[newy][newx]=1; //标记走过 top++; ifnext=1; //这一次存在可以往下走的坐标 break; } } } if(ifnext) continue; //既然存在 可以往下走的坐标 那就不需要回溯了，跳过下面代码从头开始 top--; // 不存在可以往下走的坐标 那就要回溯了 栈顶指针向回走 nowy=mstate[top-1][0];nowx=mstate[top-1][1]; //回到上一个坐标，前面提到栈顶指针，指向栈顶元素的下一个位置 所以当前栈顶元素就top-1 oriby=mstate[top][0];oribx=mstate[top][1]; //top-1指向当前的栈顶元素，那么top指向的就是刚刚的栈顶元素 flag[oriby][oribx]=0; //把刚才回溯过来的点标记为没走过 p=whatp(oriby-nowy,oribx-nowx); //这里相当于计算出dy，dx，可以重写到函数定义处看看解释 //计算p值就是为了防止我下一次又走向刚刚回溯过来的点，陷入死循环 } if(count==0) cout<<-1; //没有路径输出-1 return 0; } ```

``` #include<cstdio> #include<iostream> using namespace std; int posit[16][16]; int flag[16][16]; int end1,end2; int dy[4]={0,-1,0,1}; int dx[4]={-1,0,1,0}; int n,m; int count=0; string dfs(int y,int x,string s){ char tmp[12]; if(y!=end1||x!=end2) { sprintf(tmp,"(%d,%d)->",y,x); s+=tmp; } else{ sprintf(tmp,"(%d,%d)",y,x); cout<<s<<tmp<<endl; count++; return ""; } int newy,newx; for(int i=0;i<4;++i){ newy=y+dy[i]; newx=x+dx[i]; if(newy>=1&&newy<=n&&newx>=1&&newx<=m&&posit[newy][newx]!=0&&flag[y][x]!=1){ flag[y][x]=1; dfs(newy,newx,s); flag[y][x]=0; } } return s; }; int main(){ cin>>n>>m; int be1,be2; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) cin>>posit[i][j]; cin>>be1>>be2>>end1>>end2; dfs(be1,be2,""); if(count==0) cout<<-1; return 0; } ```

回溯, 注:本题需要按照左上右下进行移动, 不然结果会被误判? 😕(没错, 我就没看见这个qwq ```C++ #include <cstdio> #include <vector> #include <functional> #include <utility> using namespace std; int main() { int n, m; scanf("%d %d", &n, &m); vector<vector<char>> map(n, vector<char>(m)); vector<vector<char>> ita(n, vector<char>(m)); for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) { int tmp; scanf("%d", &tmp); map[i][j] = tmp; // 1 可以走, 0 不可以走 } int s_x, s_y, e_x, e_y; scanf("%d %d", &s_y, &s_x); scanf("%d %d", &e_y, &e_x); --s_x, --s_y, --e_x, --e_y; bool tag = 1; int fx[4][2] = { {0, -1}, {-1, 0}, {0, 1}, {1, 0} }; vector<pair<int, int>> lj; // 路径 (i, j) function<void(int, int)> dfs = [&](int i, int j) { if (i < 0 || j < 0 || i >= n || j >= m) return; if (ita[i][j] || !map[i][j]) return; // 之前走过 || 不能走 if (i == e_y && j == e_x) { // 输出 for (int i = 0; i < lj.size(); ++i) { printf("(%d,%d)->", lj[i].first + 1, lj[i].second + 1); } printf("(%d,%d)\n", e_y + 1, e_x + 1); tag = 0; return; } ita[i][j] = 1; lj.push_back({i, j}); for (auto& it : fx) { dfs(i + it[0], j + it[1]); } lj.pop_back(); ita[i][j] = 0; }; dfs(s_y, s_x); if (tag) printf("-1\n"); return 0; } ```

//模板 include using namespace std; define endl '\n' define INF 0x3f3f3f3f3f3f3f3f //移动向量 int dx[4] = {-1,0,1,0}; int dy[4] = {0,-1,0,1}; //创建迷宫 int a[42][42]; //起点终点 pair Start; pair End; //迷宫大小 int n,m; //方案总数 int flag = 0; //第一次 int diyici = 1; //该点是否来过 bool coming[42][42]; //路线 vector > Path; void dfs(pair now) { if(now == End) { Path.push_back(End); for(int i = 0 ; i "; } cout = 0 && nex = 0 && ney > n >> m; for(int i = 0 ; i > a[i][j]; } } //起点和终点 int First,Second; //(y,x) //first -- y //second -- x //起点 cin >> First >> Second; Start.first = First - 1; Start.second = Second - 1; //终点 cin >> First >> Second; End.first = First - 1; // y End.second = Second - 1; // x / r(int i = 0 ; i < n ; i++) { 1 = for(int j = 0 ; j < m ; j++) { 1 = cout << a[i][j]; } } cout << "(" << Start.first << "," << Start.second << ")" ; cout << "(" << End.first << "," << End.second << ")" ; auto temp = make_pair(1,1); if(Start == temp) { cout << endl << "Right compare" << endl; } / dfs(Start); if(flag == 0) { cout << "-1"; } return 0; }

DFS遍历每条路并回溯，用vector存放坐标 ``` #include <bits/stdc++.h> using namespace std; typedef pair<int,int> PII; vector<PII> v; const int N = 20; int mp[N][N]; int vis[N][N]; int n,m; int sx,sy; int x2,y2; int dx[] = {0,-1,0,1}; int dy[] = {-1,0,1,0}; int flag = 0; void dfs(int x,int y){ vis[x][y] = 1; if (x == x2 && y == y2) { flag = 1; printf("(%d,%d)",sx,sy); for (int i = 1; i < v.size() - 1; ++i){ printf("->(%d,%d)",v[i].first,v[i].second); } printf("->(%d,%d)\n",x2,y2); } for (int i = 0; i < 4; ++i) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx < 1 || nx > n || ny < 1 || ny > m) continue; if (vis[nx][ny]) continue; if (mp[nx][ny] == 0) continue; vis[nx][ny] = 1; v.push_back({nx,ny}); dfs(nx,ny); v.pop_back(); vis[nx][ny] = 0; } return; } int main(){ scanf("%d %d",&n,&m); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { cin >> mp[i][j]; } } scanf("%d %d",&sx,&sy); scanf("%d %d",&x2,&y2); v.push_back({sx,sy}); dfs(sx,sy); if(flag == 0) printf("-1\n"); return 0; } ```