给你一个由0和1构成的矩阵,其中0是墙面,1是道路,现在给你起点的位置(x0,y0),终点的位置(x1,y1),问你从起点到终点最近的路是多少。
如果不能到达输出-1。
保证起点和终点位置都是1。
本题包含若干组测试数据。
第一行六个整数n,m,x0,y0,x1,y1表示这个地图的大小,起点位置,终点。
接下来n行,每行m个数,表示这个地图的样子。
满足1<=n,m<=100
对于每组测试数据,输出最近的路,否则输出-1.
3 3 1 1 3 3 100 100 111 3 3 1 1 3 3 100 000 111
4 -1
题解
BFS的裸题嘛,如果你不会代码,那就仔细研读我的代码吧。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3+6;
int n,m,x0,yy0,x1,yy1;
int mp[maxn][maxn];
string s[maxn];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int check(int x,int y){
if(x<0||x>=n)return false;
if(y<0||y>=m)return false;
if(mp[x][y]!=-1)return false;
if(s[x][y]=='0')return false;
return true;
}
void solve(){
x0--,yy0--,x1--,yy1--;
for(int i=0;i<n;i++)
cin>>s[i];
memset(mp,-1,sizeof(mp));
queue<int> QX,QY;
QX.push(x0);
QY.push(yy0);
mp[x0][yy0]=0;
while(!QX.empty()){
int nowx=QX.front();
int nowy=QY.front();
QX.pop(),QY.pop();
for(int i=0;i<4;i++){
int nex=nowx+dx[i];
int ney=nowy+dy[i];
if(check(nex,ney)){
mp[nex][ney]=mp[nowx][nowy]+1;
QX.push(nex);
QY.push(ney);
}
}
}
printf("%d
",mp[x1][yy1]);
return;
}
int main(){
while(cin>>n>>m>>x0>>yy0>>x1>>yy1)
solve();
return 0;
}