Ac 1101. 献给阿尔吉侬的花束

刚开始看到这个题，我第一个想到的是bfs，都是经典套路了，遇到距离最短就用bfs，但是求解的过程不是很顺利
因为之前用递归实现了类似bfs的一种方式，就是标记是否走过，然后以前是类似于flood fill填充吧，就是求某一区间可以走多少个格子，或者某一封闭区间的面积。
代码如下

#include<iostream>
#include<algorithm>
using namespace std;
const int N=210;
const int Inf=0x3f3f3f3f;
int n,m,sx,sy,flag=0;
char g[N][N];
int dx[4]={
    1,-1,0,0} ,dy[4]={
    0,0,1,-1};
void bfs(int x,int y,int b)
{
    if(g[x][y]=='E'){
    flag=min(flag,b);return;}g[x][y]='#';for(int k=0;k<4;k++){
    int tx=x+dx[k];int ty=y+dy[k];if(tx<0||ty<0||tx>=n||ty>=m)continue;if(g[tx][ty]!='#')bfs(tx,ty,b+1);}return;
}
int main(void)
{
    int T;cin>>T;while(T--){
    cin>>n>>m;for(int i=0;i<n;i++)cin>>g[i];for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(g[i][j]=='S'){
    sx=i;sy=j;break;}flag=Inf;bfs(sx,sy,0);if(flag!=Inf)cout<<flag<<endl;elsecout<<"oop!"<<endl;}
}

然后结果

WA
后来我的仔细分析下，用递归可以实现bfs的某些功能（比如说填充），但是没法实现保存走过的点，并从这些节点找下一个节点。因为题目要求最小距离。我想到了平时标记的book改成dist，这样表示已经走过的距离还能表示是否走过，于是，我写出了成功AC的代码。

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
const int N=210;
int n,m,sx,sy;
char g[N][N];
int dist[N][N];
int dx[4]={
    0,1,0,-1},dy[4]={
    1,0,-1,0};
int bfs(int a,int b)
{
    memset(dist,-1,sizeof(dist));PII l;l.x=a;l.y=b;dist[a][b]=0;queue<PII> q;q.push(l);while(q.size()){
    auto t=q.front();q.pop();for(int i=0;i<4;i++){
    int tx=t.x+dx[i];int ty=t.y+dy[i];if(tx<0||ty<0||tx>=n||ty>=m||dist[tx][ty]!=-1||g[tx][ty]=='#')continue;if(g[tx][ty]=='E')return dist[t.x][t.y]+1;dist[tx][ty]=dist[t.x][t.y]+1;q.push({
    tx,ty});}}return 0;
}
int main(void)
{
    int T;cin>>T;while(T--){
    cin>>n>>m;for(int i=0;i<n;i++) cin>>g[i];for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(g[i][j]=='S'){
    sx=i;sy=j;break;}if(bfs(sx,sy))cout<<bfs(sx,sy)<<endl;elsecout<<"oop!"<<endl;}
}