[Acwing] bfs路径输出

问题

解决 最短路路径输出问题

思路:

用一个pre数组 来实现是从哪个点转移的即可

Code

#include 
#define x first
#define y second
using namespace std;
typedef pair PII;
const int N = 1500;
int a[N][N],st[N][N],n;
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};
PII pre[N][N];
int ans[N][2];

struct node
{
    int x,y;
};
void bfs()
{
    /// cout