S为入口
E为出口
#为障碍
-为可通过路径
思路：通过BFS进行广搜，若搜到即为最短路径，若搜不到则不存在（当节点队列为空时）
代码：
#include<iostream> #include<queue> #include<cstring> using namespace std; class Point{ public: Point(){ vis = 0; }; Point(const Point& p){ x = p.x; y = p.y; data = p.data; vis = p.vis; }; public: int x; int y; int vis; char data; }; Point mp[110][110]; int height,width;; int x_move[4] = {-1,1,0,0}; int y_move[4] = {0,0,-1,1}; bool check(Point p){ if(p.x >= 1 && p.x <= width && p.y >= 1 && p.y <= height){ if(p.data == '-' || p.data == 'E'){ mp[p.x][p.y].vis = 1; return true; } } return false; } void BFS(Point &op){ int sum[110][110]; memset(sum,0,sizeof(sum)); queue<Point> q; q.push(op); int flag = 0; while(!q.empty()){ Point p = q.front();q.pop(); for(int i = 0;i < 4;i++){ int x = p.x,y = p.y; x += x_move[i];y += y_move[i]; if(!mp[x][y].vis && check(mp[x][y])) { q.push(mp[x][y]);sum[x][y] = sum[p.x][p.y] + 1; if(mp[x][y].data == 'E'){ cout<<sum[x][y]<<endl; return; } } } } cout<<-1<<endl; return; } void initial(){ for(int i = 0;i <= 100;i++) for(int j = 0;j <= 100;j++) { mp[i][j].vis = 0; } } int main(){ int n; cin>>n; while(n--){ Point op; initial(); cin>>height>>width; for(int i = 1;i <= height;i++) for(int j = 1;j <= width;j++) { cin>>mp[i][j].data; mp[i][j].x = i;mp[i][j].y = j; if(mp[i][j].data == 'S')op = mp[i][j]; } BFS(op); } }
