信息学奥赛一本通T1252-走迷宫-题解（C++代码）（最基础的广搜模板）

解题思路:就是用广度优先搜索，十分简单

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

char mp[101][101];//设置地图

int book[101][101];//标记地图

int r,c,i,j;

int dir[4][2]={0,1,0,-1,-1,0,1,0};//上下左右

struct state{

int x;

int y;

int step;

};

queue<state> q;

bool panduan(state s){   //判断出没出地图边界或者走没走过该地方

if(!book[s.x][s.y]&&s.x>=0&&s.x<r&&s.y>=0&&s.y<c&&mp[s.x][s.y]=='.')

return true;

return false;

}

int bfs(state st){    //开始搜索

state now,next;

while(!q.empty()){

now=q.front();

q.pop();

if(now.x==r-1&&now.y==c-1){

return now.step;

}

for(i=0;i<4;i++){

next.x=now.x+dir[i][0];

next.y=now.y+dir[i][1];

next.step=now.step+1;

if(panduan(next)){

q.push(next);

book[next.x][next.y]=1;

}

}

}

return -1;

}

int main(){

int ans=0;

state st;

cin>>r>>c;

for(i=0;i<r;i++){

for(j=0;j<c;j++){

cin>>mp[i][j];

if(mp[i][j]=='#'){

book[i][j]=1;

}

}

}

st.x=0;

st.y=0;

st.step=0;

book[st.x][st.y]=1;

q.push(st);

cout<<bfs(st)+1;

}