题意： 给定一个n*m的图，途中的’S’为起点，‘E’为终点。每次移动只能横向或纵向地移向最近的一个干净的点’.'或终点，'X’为脏的点。如果能到达终点，则输出步数最少并且字典序最小的路径（下移为D、左移为L、右移为R、上移为U）。否则输出-1。
曲折经历： 比赛时想的没有那么周到，用BFS+DFS，结构体里携带各种参数，并且实时传递移动路径，导致空间占用比较大，加上本来算法的效率就不高，所以WA的和TLE的次数累计到达了13发。最后各种修改，卡常1980ms极限AC。又因为参加过这个比赛和做过这个题目的人很少，我甚至找不到题解可以学习。所以自己又花了一个上午的时间研究，最后得出一个时间和空间以及代码长度都最优的代码（对我的能力而言）
最终思路：
BFS。 众所周知：一个图 + 起点到终点 + 最短路径 = BFS。定义一个结构体的队列，结构体node中只需携带某个点的坐标即可。定义vis[][] 避免重复访问。pre_x[][]、pre_y[][]。 因为广搜的特性，从某个点出发，最多可能有四个可达的目标点。而因为vis避免重复访问，每个点一定只能来自于一个点。所以定义两个数组来记录某一个干净的点的前驱节点的坐标。DFS。 用BFS一直搜索到终点，结束广搜。我们记录路径的方式是用两个pre数组记录前驱节点的坐标，并没有记录移动的方向。所以可以通过dfs从终点递推回起点，比较每个点与前驱节点的坐标关系，记录下移动方向。最后倒叙输出答案即可。 #include<bits/stdc++.h> using namespace std; const int N = 2e3 + 10; int n, m; int sx, sy, cnt; //sx\sy记录起点坐标。cnt为路径的字符个数 int pre[N][N]; int pre_x[N][N]; //记录前驱节点的坐标 int pre_y[N][N]; int vis[N][N]; //访问标记，避免重复访问 char G[N][N]; //存图 char ans[2 * N]; //记录路径 int dir[][2] = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}}; char Dir[] = "DLRU"; struct node { int x, y;}; int check(int x, int y) { //检查移动后是否还在图的范围内 if(x < 1 || x > n || y < 1 || y > m) return 0; return 1; } void dfs(int x, int y) { //从终点推回起点，标出移动路径 if(x == sx && y == sy){ //回到起点，输出答案 cout << cnt << endl; for(int i = cnt - 1; i >= 0; i--) cout << ans[i]; return; } int prex = pre_x[x][y]; int prey = pre_y[x][y]; ans[cnt++] = Dir[pre[x][y]]; dfs(prex, prey); } void BFS() { queue<node> Q; Q.push({sx, sy}); vis[sx][sy] = 1; while(!Q.empty()) { node u = Q.front(); Q.pop(); if(G[u.x][u.y] == 'E') { //找到终点，dfs找到移动路径 dfs(u.x, u.y); return ; } for(int i = 0; i < 4; i++) { int nex = u.x + dir[i][0]; int ney = u.y + dir[i][1]; while(check(nex, ney)) { if(vis[nex][ney]) break; if(G[nex][ney] == '.' || G[nex][ney] == 'E'){ vis[nex][ney] = 1; pre[nex][ney] = i; pre_x[nex][ney] = u.x; pre_y[nex][ney] = u.y; Q.push({nex, ney}); break; //找到最近的第一个干净点，插入队列即可推出 } //干净点不一定相邻，可能隔着几个'X'才能到达，所以需要不断移动查找 nex += dir[i][0], ney += dir[i][1]; } } } cout << -1 << endl; } int main() { ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) { cin >> G[i][j]; if(G[i][j] == 'S') sx = i, sy = j; } BFS(); return 0; }