最少步數
時間限制：
3000 ms ?|? 內存限制：
65535 KB 難度：
4
描述
這有一個迷宮，有0~8行和0~8列：
?1,1,1,1,1,1,1,1,1
?1,0,0,1,0,0,1,0,1
?1,0,0,1,1,0,0,0,1
?1,0,1,0,1,1,0,1,1
?1,0,0,0,0,1,0,0,1
?1,1,0,1,0,1,0,0,1
?1,1,0,1,0,1,0,0,1
?1,1,0,1,0,0,0,0,1
?1,1,1,1,1,1,1,1,1
0表示道路，1表示墻。
現在輸入一個道路的坐標作為起點，再如輸入一個道路的坐標作為終點，問最少走幾步才能從起點到達終點？
（注：一步是指從一坐標點走到其上下左右相鄰坐標點，如：從（3，1）到（4,1）。）
輸入 第一行輸入一個整數n（0<n<=100），表示有n組測試數據;
隨后n行,每行有四個整數a,b,c,d（0<=a,b,c,d<=8）分別表示起點的行、列，終點的行、列。 輸出 輸出最少走幾步。 樣例輸入 2
3 1 5 7
3 1 6 7 樣例輸出 12
11
來源 [苗棟棟]原創 上傳者 苗棟棟
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int mg[9][9]=
{1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,1,0,1,1,0,0,1,1,0,0,0,1,1,0,1,0,1,1,0,1,1,1,0,0,0,0,1,0,0,1,1,1,0,1,0,1,0,0,1,1,1,0,1,0,1,0,0,1,1,1,0,1,0,0,0,0,1,1,1,1,1,1,1,1,1,1
};
int visit[9][9];struct num
{int x,y,step;
};
queue<num> Q;
int bfs(int x1,int y1,int x2,int y2)
{num e= {x1,y1,0};visit[x1][y1]=1;//標記走過Q.push(e);while(!Q.empty()){e=Q.front();//取隊首，進行判斷是否可走if(e.x==x2&&e.y==y2)break;//走到終點Q.pop();int l,r;for(int i=0; i<4; i++){switch(i){case 0:l=e.x;r=e.y+1;break;case 1:l=e.x+1;r=e.y;break;case 2:l=e.x;r=e.y-1;break;case 3:l=e.x-1;r=e.y;break;}if(l>=0&&l<=8&&r>=0&&r<=8&&visit[l][r]==0&&mg[l][r]==0){num e1= {l,r,e.step+1};Q.push(e1);visit[l][r]=1;}}}while(!Q.empty()){Q.pop();}return e.step;
}
int main()
{int n;cin>>n;while(n--){memset(visit,0,sizeof(visit));int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;int st= bfs(x1,y1,x2,y2);cout<<st<<endl;}return 0;
}
《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀
總結
以上是生活随笔為你收集整理的最少步数的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
