输入一个迷宫的长,宽,起始点,终点,迷宫内容(0代表不能走,1反之),返回是否有解(bool)
#include<bits/stdc++.h>
using namespace std;
const int maxn=101;//迷宫最高大小;
int mg[maxn][maxn];//迷宫;
int sizhou[4][2]={{1,0},{0,1},{-1,0},{0,-1}};//四周位置;
bool visit[maxn][maxn];//是否走过 ;
int sx,sy,ex,ey,n,m;//起始点x、y,终点x、y,长(x),宽(y);
deque<int>x;//队列x坐标;
deque<int>y;//队列y坐标;
int k(int sx,int sy,int ex,int ey){//查询函数;
x.push_back(sx);//从起始点出发;
y.push_back(sy);//同上;
while(!x.empty()){
int bx=x.front();//设游标;
int by=y.front();//同上;
visit[bx][by]=1;//标记;
for(int i=0;i<4;i++){//遍历游标四周;
int pbx=bx+sizhou[i][0];//目前位置;
int pby=by+sizhou[i][1];//同上;
if(pbx<n && pbx>=0 && pby < m && pby >= 0 && mg[pbx][pby]!=0 && visit[pbx][pby]==0){//是否不出格且可以走且没走过;
if(pbx==ex && pby == ey)return 1;//是否到终点;
x.push_back(pbx);//添加位置;
y.push_back(pby);//同上;
visit[pbx][pby]=1;//标记;
}
}
x.pop_front();//踢掉游标;
y.pop_front();//同上;
}
return 0;
}
int main(){
memset(visit,0,sizeof(visit));//初始化;
cin >> n >> m;
cin >> sx >> sy >> ex >> ey;
for(int i=1;i<=n;i++){//输入迷宫;
for(int j=1;j<=m;j++){
cin >> mg[i][j];
}
}
cout << k(sx,sy,ex,ey);
return 0;
}
/*
主体框架
int k(int sx,int sy,int ex,int ey){
队伍初始化;
for(队伍不为空){
设置作用点;
设为走过 ;
for(遍历身边){
if(条件){
if(在终点){
return 1;
}
移到队尾;
设为走过;
}
}
删队头;
}
return 0;
}
int main(){
获取数据;
cout << k(sx,sy,ex,ey);
return 0;
}
*/