SSL 1455 电子老鼠闯迷宫

• 样例错了，输出为 27。

这一题就是一道裸的广搜，主要就是考虑路径输出。
我们需要一个 p r e i pre_i prei​ ，记录节点 i i i 在广搜中是由哪个节点转移的，然后最后用递归一步步倒推输出，即可处理路径问题。
输出路径函数：

void print(int p)
{
	if(p==1)
	  {
	  	cout<<"("<";
	  	return ;
	  }
	print(pre[p].fa);
	cout<<"("<";
	return ;
}

函数的作用为输出从根节点到 p p p 的路径。

#include 
#include 
#include 
using namespace std;
int n,SX,SY,FX,FY;
int a[1001][1001]={0};
struct Gar
{
	int x,y,step,s;
	Gar(int xx,int yy,int st,int ss):x(xx),y(yy),step(st),s(ss) {}
};
struct qwq
{
	int x,y,fa;
};
qwq pre[1000010];
const int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
bool vis[1001][1001]={false};
queue q;

void print(int p)
{
	if(p==1)
	  {
	  	cout<<"("<";
	  	return ;
	  }
	print(pre[p].fa);
	cout<<"("<";
	return ;
}

void bfs(int sx,int sy,int fx,int fy)
{
	vis[sx][sy]=true;
	q.push(Gar(sx,sy,1,1));
	int f=1;
	pre[f].x=sx;
	pre[f].y=sy;
	pre[f].fa=0;
	while(!q.empty())
	  {
	  	Gar u=q.front();
	  	q.pop();
	  	if(u.x==fx&&u.y==fy)
	  	  {
	  	  	print(pre[u.s].fa);
	  	  	cout<<"("<n||ny<=0||ny>n) continue;
		  	if(a[nx][ny]==1) continue;
		  	if(vis[nx][ny]) continue;
		  	vis[nx][ny]=true;
		  	q.push(Gar(nx,ny,u.step+1,f+1));
		  	f++;
		  	pre[f].x=nx;
		  	pre[f].y=ny;
		  	pre[f].fa=u.s;
		  }
	  }
	return ;
}
int main()
{
	cin>>n;
	cin>>SX>>SY>>FX>>FY;
	for(int i=1;i<=n;i++)
	  {
	  	for(int j=1;j<=n;j++)
	  	  cin>>a[i][j];
	  }
	bfs(SX,SY,FX,FY);
	return 0;
}