題目描述
給定一個N×M?的網格迷宮?G。G?的每個格子要么是道路，要么是障礙物（道路用?11表示，障礙物用?0?表示）。
已知迷宮的入口位置為?(x1?,y1?)，出口位置為?(x2?,y2?)。問從入口走到出口，最少要走多少個格子。
輸入描述
輸入第?11?行包含兩個正整數 N,M，分別表示迷宮的大小。
接下來輸入一個?𝑁×𝑀N×M?的矩陣。若 Gi,j?=1?表示其為道路，否則表示其為障礙物。
最后一行輸入四個整數?𝑥1,𝑦1,𝑥2,𝑦2表示入口的位置和出口的位置。
1≤N,M≤102，0≤Gi,j?≤1，1≤x1?,x2?≤N，1≤y1?,y2?≤M。
輸出描述
輸出僅一行，包含一個整數表示答案。
若無法從入口到出口，則輸出??1；
輸入輸出樣例
示例 1
輸入
5 5
1 0 1 1 0
1 1 0 1 1
0 1 0 1 1
1 1 1 1 1
1 0 0 0 1
1 1 5 5
輸出
8
運行限制
- 最大運行時間：1s
- 最大運行內存: 128M
代碼為：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=1e2+10;
int n,m;
int x2,y2;//出口的位置
int g[N][N];//存儲地圖
int dist[N][N];//每個點到起點的距離
queue<PII> q;//存坐標
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};int bfs(int x1,int y1)
{memset(dist,-1,sizeof dist);//初始都為-1q.push({x1,y1});dist[x1][y1]=0;while(!q.empty()){auto Top=q.front();//取出對頭q.pop();//彈出對頭for(int i=0;i<4;i++){int a=Top.x+dx[i];int b=Top.y+dy[i];//入口的位置的下一個位置if(a<0||a>n||b<0||b>m) continue;//越界if(g[a][b]!=1) continue;//不是道路if(dist[a][b]>1) continue;q.push({a,b});dist[a][b]=dist[Top.x][Top.y]+1;if(a==x2&&b==y2) return dist[x2][y2];}}return -1;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);int x1,y1;//入口的位置cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)cin>>g[i][j];}cin>>x1>>y1>>x2>>y2;int res=bfs(x1,y1);cout<<res<<'\n';return 0;
}優化后的代碼（運行時間1ms）：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=1e2+10;
int n,m;
int x2,y2;//出口的位置
int g[N][N];//存儲地圖
int dist[N][N];//每個點到起點的距離
queue<PII> q;//存坐標
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};int bfs(int x1,int y1)
{memset(dist,-1,sizeof dist);//初始都為-1q.push({x1,y1});dist[x1][y1]=0;while(!q.empty()){auto Top=q.front();//取出對頭q.pop();//彈出對頭for(int i=0;i<4;i++){int a=Top.x+dx[i];int b=Top.y+dy[i];//入口的位置的下一個位置if(a<0||a>n||b<0||b>m) continue;//越界if(g[a][b]!=1) continue;//不是道路if(dist[a][b]>1) continue;q.push({a,b});dist[a][b]=dist[Top.x][Top.y]+1;if(a==x2&&b==y2) return dist[a][b];}}return -1;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);int x1,y1;//入口的位置cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)cin>>g[i][j];}cin>>x1>>y1>>x2>>y2;int res=bfs(x1,y1);cout<<res<<'\n';return 0;
}
)
