题目链接：http://ybt.ssoier.cn:8088/problem_show.php?pid=1251
1 #include<bits/stdc++.h> 2 using namespace std; 3 int m, n; 4 char mp[25][25]; 5 int sx, sy, ex, ey; 6 struct node{ //结构体定义位置坐标和起点开始步骤 7 int x, y, step; 8 }; 9 int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; //二维数组定义上下左右方向位移量 10 node que[10010]; //结构体数组存放队列 11 int f, r; //队首和队尾定义 12 void bfs(){ 13 int ans=-1; 14 f=r=1; //队列初始化 15 que[r].x=sx; que[r].y=sy; que[r].step=0; mp[sx][sy]='#';//初始位置入队 16 while(f<=r){ 17 int fx=que[f].x, fy=que[f].y, fs=que[f].step;//获取队首信息 18 if(fx==ex && fy==ey){//判断是否到达目标 19 ans=fs; 20 break; 21 } 22 for(int i=0; i<4; i++){//遍历四个方向 23 int nx=fx+dir[i][0]; 24 int ny=fy+dir[i][1]; 25 if(nx>=0 && nx<m && ny>=0 && ny<n && (mp[nx][ny]=='.' || mp[nx][ny]=='*')){//判断是否满足入队条件 ，注意此处终点排除‘T’ 26 mp[nx][ny]='#';//更改状态避免重复入队 27 r++;//队尾后移准备入队 28 que[r].x=nx;//入队 29 que[r].y=ny; 30 que[r].step=fs+1;//步骤加1 31 } 32 } 33 f++;//队首后移出队 34 } 35 cout<<ans<<endl; 36 37 } 38 int main() 39 { 40 while(1){ 41 cin>>m>>n; 42 if(m==0 && n==0)break; 43 for(int i=0; i<m; i++)cin>>mp[i]; 44 for(int i=0; i<m; i++) 45 for(int j=0; j<n; j++){ 46 if(mp[i][j]=='@')sx=i, sy=j; 47 if(mp[i][j]=='*')ex=i, ey=j; 48 } 49 bfs(); 50 } 51 return 0; 52 }