解题思路:
几乎可以说是一个模板题目,记得收藏这种模板,BFS的模板
参考代码:
#include<bits/stdc++.h> #define hh ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; const int maxn=105; char mp[maxn][maxn]; int vis[maxn][maxn]; const int dir[4][2]= {0,1,0,-1,1,0,-1,0}; //方向向量 右,左,下,上 int t,n,m; int out_x,out_y; struct state { int x,y; int step; }; bool check(state s) { if(!vis[s.x][s.y]&&s.x<n&&s.y<m&&s.x>=0&&s.y>=0) { return true; } return false; } int bfs(state st) { queue<state> q; state now,next; st.step=0; q.push(st); vis[st.x][st.y]=1; while(!q.empty()) { now=q.front(); if(now.x==out_x&&now.y==out_y) { return now.step; } for(int i=0; i<4; i++) { next.x=now.x+dir[i][0]; next.y=now.y+dir[i][1]; next.step=now.step+1; if(check(next)) { q.push(next); vis[next.x][next.y]=1; } } //state temp=q.front(); //printf("%d %d %d\n",temp.x,temp.y,temp.step); q.pop(); } return -1; } int main() { hh; cin>>t; while(t--) { state st; memset(mp,0,sizeof(mp)); memset(vis,0,sizeof(vis)); cin>>n>>m; for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { cin>>mp[i][j]; if(mp[i][j]=='S') { st.x=i; st.y=j; st.step=0; } if(mp[i][j]=='E') { out_x=i,out_y=j; } if(mp[i][j]=='#'){ vis[i][j]=1; } } } cout<<bfs(st)<<endl; /*for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cout<<vis[i][j]<<' '; } cout<<endl; } */ } return 0; }
0.0分
4 人评分
UDP广播协议叫吃饭 2020-07-21 23:49:03 |
解除绑定IO流的,是#define hh ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)提供的,你可以理解为输入这句话可以加速数据的读入和输出,这对于大数据是很有帮助的