献给阿尔吉侬的花束

思路

常规 BFS 即可解决问题。

从 S 出发进行 BFS ，试图四个方向的扩展，对点进行边界检查以及 st 检查（这里没有用 st 数组而是利用 dist 是否为 INF 来判断是否经过），如果在边界内且未经过，更新距离并入队。

检查当前更新的点是否为终点，如果为终点则输出距离，并返回函数。

队列为空后，输出 oop即可。

注意

1. 终点定义起初用的是 end ，但是会出现 [Error] reference to 'end' is ambiguous
2. 注意每次 BFS 之前 memset 填充 g ,dist

代码

#include<bits/stdc++.h>
using namespace std;
const int N=210;
int g[N][N],st[N][N],dist[N][N];
int n,m;
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
typedef pair<int,int>PII;
PII start,ed;
int T;
void bfs(){
    queue<PII>q;
    q.push(start);
    int x=start.first,y=start.second;
    dist[x][y]=0;
    while(q.size()){
        auto fr=q.front();
        q.pop();
        int x=fr.first,y=fr.second;
        for(int i=0;i<4;i++){
            int x1=x+dx[i],y1=y+dy[i];
            if(x1>=1 and x1<=n and y1>=1 and y1<=m and g[x1][y1]!=-1 and dist[x1][y1]==0x3f3f3f3f){
                dist[x1][y1]=dist[x][y]+1;
                q.push({x1,y1});
            }
            if(x1==ed.first and y1==ed.second){
            cout<<dist[x1][y1]<<endl;
            return ;
            }
        }
    }
    cout<<"oop!"<<endl;//opp笑嘻了，看了半天才发现
}
int main(){
    cin>>T;
    while(T--){
        cin>>n>>m;
        memset(g,0,sizeof g);
        memset(dist,0x3f,sizeof dist);
        char ch;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>ch;
                if(ch=='S')start={i,j};
                else if(ch=='#')g[i][j]=-1;
                else if (ch=='E')ed={i,j};
            }
        }
        bfs();
    }
}

其他

高中有个女同学送了我一本书，如题《献给阿尔吉侬的花束》，当时浅浅读了一下，讲述了一个因脑部手术过后而智商变得极高，旋即又逐渐衰退成正常人的故事。

如今它仍在书柜陈列着，有机会回去再看一下。