HPU暑期第五次积分赛 - G-迷宫（BFS+最短路径）

题目

代码

#include <iostream> #include <cstdio> #include <queue> #include <cstring> using namespace std; int mp[110][110];//做标记 int dir[2][4]={{1,-1,0,0},{0,0,1,-1}};// 移动 int n,m,t; char st[110][110]; struct node {int x,y;int step; }; int BFS(int x,int y) {queue<node> que;node u,v;u.x=x;u.y=y;u.step=0;mp[x][y]=1;que.push(u);while(!que.empty()){v=que.front();que.pop();if(st[v.x][v.y]=='t') return v.step;for(int i=0;i<4;i++){u.x=v.x+dir[0][i];u.y=v.y+dir[1][i];if((0<=u.x && u.x<n) && (0<=u.y && u.y<m)&&(mp[u.x][u.y]!=1)&&(st[u.x][u.y]!='#')){mp[u.x][u.y]=1;u.step=v.step+1;que.push(u);}}}return -1; } int main() {int i,j;while(cin>>n>>m){memset(mp,0,sizeof(mp));memset(st,0,sizeof(st));for(i=0;i<n;i++)for(j=0;j<m;j++)cin>>st[i][j];for(i=0;i<n;i++){for(j=0;j<m;j++){if(st[i][j]=='s'){cout<<BFS(i,j)<<endl;break;}}}}return 0; }

总结

以上是生活随笔为你收集整理的HPU暑期第五次积分赛 - G-迷宫（BFS+最短路径）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。