迷宫寻宝

题目：

题解：

bfs模板

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<sstream>
#include<vector>
#include<ctime>
#include<list>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
int res,flag;
struct node{
  int x,y,step;
};
int dx[5]={0,0,1,-1};
int dy[5]={1,-1,0,0};
queue<node>q;
char pos[1007][1007];
bool vis[1007][1007];
void bfs(int x1,int y1,int x2,int y2,int n){
  while(!q.empty()) q.pop();
  struct node now,next;
  now.x=x1,now.y=y1;
  now.step=0;
  vis[now.x][now.y]=1;
  q.push(now);
  while(!q.empty()){
    now=q.front();
    q.pop();
    if(pos[now.x][now.y]=='E'){
      flag=1;
      res=min(res,now.step);
      continue;
    }
    for(int i=0;i<4;i++){
      next.x=now.x+dx[i];
      next.y=now.y+dy[i];
      if(vis[next.x][next.y]==1||pos[next.x][next.y]=='#'||next.x<0||next.x>=n||next.y<0||next.y>=n){
        continue;
      }
        next.step=now.step+1;
        vis[next.x][next.y]=1;
        q.push(next);
    }
  }
}
int main()
{
  int n;
  while(cin>>n){
    res=inf,flag=0;
    memset(vis,0,sizeof(vis));
    int x1,y1,x2,y2;
    for(int i=0;i<n;i++){
      getchar();
      for(int j=0;j<n;j++){
        //getchar();
        scanf("%c",&pos[i][j]);
        if(pos[i][j]=='S'){
          x1=i,y1=j;
        }
        else if(pos[i][j]=='E'){
          x2=i,y2=j;
        }
      }
    }
    bfs(x1,y1,x2,y2,n);
    if(flag==1) cout<<res<<endl;
    else cout<<"-1"<<endl;
  }
  return 0;
}