Solution
数据范围很小，一共才\(5\times5\)，所以乱搞做法很多
比如我一开始就先bfs单纯跑最短路，然后dfs找路径 但是忘回溯被嘲讽
其实可以边bfs边记录路径，因为bfs是按层数搜的，所以第一次到达终点的路径一定是最优的。
那么如何记录路径呢？我原来用pair，经教练指导发现可以用字符串记录，bfs 队列queue中传三个参数：x，y,和str（路径），具体实现见代码吧：
Code
std：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <string>
#define N 1010
#define INF 0x3f3f3f3f
using namespace std;
int mapp[N][N];
int vis[N][N];
struct Node
{
int x,y;
string str;
};
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
void bfs()
{
queue <Node> q;
q.push(Node{0,0});
vis[0][0] = 0;
while(!q.empty())
{
Node p = q.front();
q.pop();
if(p.x == 4 && p.y == 4) //注意我们并没有记录起点，需要单独输出一下起点
{
cout<<"(0, 0)\n";
for(int i=0;i<p.str.length();i+=2)
{
cout<<"("<<p.str[i]<<", "<<p.str[i+1]<<")"<<endl;
}
return;
}
for(int i=0;i<4;i++)
{
int ax = p.x + dx[i];
int ay = p.y + dy[i];
if(ax>=0&&ax<5&&ay>=0&&ay<5&&vis[ax][ay] == INF &&!mapp[ax][ay])
{
string str_input = p.str+char(ax+'0')+char(ay+'0');
vis[ax][ay] = vis[p.x][p.y] + 1;
q.push(Node{ax,ay,str_input});
}
}
}
}
int main()
{
for(int i=0;i<5;i++)
{
for(int j=0;j<5;j++) scanf("%d",&mapp[i][j]);
}
memset(vis,INF,sizeof(vis));
bfs();
}
另外再附上我的暴力做法吧：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define N 1010
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<int,int> PAIR;
int mapp[N][N];
int vis[N][N];
int minn_step = 0;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
PAIR l[N];
void bfs()
{
queue <PAIR> q;
q.push(PAIR(0,0));
vis[0][0] = 0;
while(!q.empty())
{
PAIR p = q.front();
q.pop();
for(int i=0;i<4;i++)
{
int ax = p.first + dx[i];
int ay = p.second + dy[i];
if(ax>=0&&ax<5&&ay>=0&&ay<5&&vis[ax][ay] == INF&&!mapp[ax][ay] )
{
q.push(PAIR(ax,ay));
vis[ax][ay] = vis[p.first][p.second] + 1;
}
}
}
}
void dfs(int x,int y,int step,PAIR s[])
{
if(x == 4 && y == 4)
{
if(step == minn_step)
{
cout<<"(0, 0)\n";
for(int i=0;i<step;i++) printf("(%d, %d)\n",s[i].first,s[i].second);
}
return;
}
for(int i=0;i<4;i++)
{
int ax = x+dx[i];
int ay = y + dy[i];
if(ax>=0&&ax<5&&ay>=0&&ay<5&&vis[ax][ay] == INF &&!mapp[ax][ay])
{
s[step].first = ax;
s[step].second = ay;
vis[ax][ay] = 1;
dfs(ax,ay,step+1,s);
vis[ax][ay] = INF;
}
}
}
int main()
{
memset(vis,INF,sizeof(vis));
for(int i=0;i<5;i++)
{
for(int j=0;j<5;j++) cin>>mapp[i][j];
}
bfs();
minn_step = vis[4][4];
memset(vis,INF,sizeof(vis));
dfs(0,0,0,l);
}