因在做完这道题时突然想到，学校oj有一道类似题目，但方法不同，遂经过改编，出次题解(bushi)

题目描述

编写一个求解迷宫问题的程序，要求输出迷宫的所有路径，并求最短路径长度及最短路径。规定：
S：迷宫的入口
D：迷宫的出口
X：障碍物，无法从这里通过
*：空地
搜索顺序优先度：↑、→、↓、←。

样例

输入#1

6
XXXXXX
XS**XX
X*X**X
X***XX
XX**DX
XXXXXX

输出#1

→→↓↓↓→
→→↓↓←↓→→
↓↓→→↓→
↓↓→↓→→
8 6

• 写法1

#define _CRT_SECURE_NO_WARNINGS 1  
#include <iostream>  
#include <vector>  
#include <queue> 
#include<string>
#include<cstring>
#include<unordered_map>
using namespace std;
typedef pair<int, int> PII;
const int N = 20;
bool flag = false;
int n, m, sx, sy, ex, ey;
char map[N][N];
bool vis[N][N];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
int minn=1e9, maxx=-1e9;
unordered_map<int, string> h{ {0, "↑"}, {1, "→"}, {2, "↓"}, {3, "←"} };
void dfs(int x, int y, vector<string>& p) {
    //p.push_back({ x,y });
    if (x == ex && y == ey) {
        int x = p.size();
        //cout << x<<endl;
        minn = min(minn, x);
        maxx = max(maxx, x);
        //flag = 1;
        int sz = (int)p.size();//XX.size() 返回的是一个 size_t 类型,size_t(~~算个知识点吧~~） 是无符号整数
        for (int i = 0; i < sz; i++) {
            //cout << '(' << p[i].first << ',' << p[i].second << ')';
            //if (i < sz - 1)cout << "->";
            cout<<p[i];
        }
        cout << endl;
    }
    else {
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >=0 && nx < n && ny >= 0 && ny < n && !vis[nx][ny] && map[nx][ny] !='X') {
                vis[nx][ny] = true;
                p.push_back(h[i]);
                dfs(nx, ny, p);
                vis[nx][ny] = false;
                p.pop_back();//整个dfs只有这里与洛谷题目不一样，注意区分
            }
        }
    }
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
            if (map[i][j] == 'S') {
                sx = i, sy = j;
            }
            else if (map[i][j] == 'D') {
                ex = i, ey = j;
            }
        }
    memset(vis, false, sizeof(vis));
    vector<string> p;
    vis[sx][sy] = true;
    dfs(sx, sy, p);
    if (minn == 1e9 && maxx == -1e9)cout << 0 << " " << 0;//特判没有路径的情况
    else cout << maxx << " " << minn ;
    return 0;
}

• 写法 2（借鉴我舍友大佬的）

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<stack>
#include<unordered_map>
#define SizeMax 50
using namespace std;
const int N = 21;
char m[N][N];
bool st[N][N];
int n,ex,ey,sx,sy;
unordered_map<int,string> h{ {0, "↑"}, {1, "→"}, {2, "↓"}, {3, "←"} };
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
int minn=1e9, maxx=-1e9;
void dfs(int x, int y,string ans) {
    st[x][y] = true;
    if (x == ex && y == ey) {
        cout << ans << endl;
        int x = ans.length();
        //cout << x<<endl;
        minn = min(minn, x);//ans.size() 返回的是一个 size_t 类型,size_t 是无符号整数
        maxx = max(maxx, x);
    }
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && nx < n && ny >= 0 && ny < n && m[nx][ny] != 'X' && st[nx][ny] == false) {
            st[nx][ny] = true;
            dfs(nx, ny,ans+h[i]);
            st[nx][ny] = false;
        }
    }
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) { 
            cin >> m[i][j];
            if (m[i][j] == 'S') {
                sx = i, sy = j;
            }
            else if (m[i][j] == 'D') {  
                ex = i, ey = j; 
            }
        }
    dfs(sx, sy,"");
    if (minn == 1e9 && maxx == -1e9)cout << 0 << " " << 0;
    else cout << maxx/3<< " " << minn/3;

    return 0;
}

两种写法差别不大，第一种是用vector[HTML_REMOVED]记录路径，第二种则更直接用string，其余回溯根据不同的特点来写，总体上是一样的