2020.2.22 排位赛 G - Bucket Brigade(BFS)

Bucket Brigade

题面

题目分析
BFS模板题

代码

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>

using namespace std;

const int INF=100000000;

typedef pair<int ,int> P;

char m[20][20];
int sx,sy;
int gx,gy;
int d[20][20];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};

int bfs()
{
 queue<P> que;
 for(int i=0;i<10;i++)
 {
  for(int j=0;j<10;j++)
  {
   d[i][j]=INF;
  }
 }
 
 que.push(P(sx,sy));
 d[sx][sy]=0;
 while(que.size())
 {
  P p = que.front();que.pop();
  if(p.first==gx&&p.second==gy)break;
  for(int i=0;i<4;i++)
  {
   int nx=p.first+dx[i],ny=p.second+dy[i];
   if(0<=nx&&nx<10&&0<=ny&&ny<10&&m[nx][ny]!='R'&&d[nx][ny]==INF){
    que.push(P(nx,ny));
    d[nx][ny]=d[p.first][p.second]+1;
   }
  }
 }
 return d[gx][gy]-1;
}

int main()
{
 for(int i=0;i<10;i++)
 {
  scanf("%s",m[i]);
 }
 for(int i=0;i<10;i++)
 {
  for(int j=0;j<10;j++)
  {
   if(m[i][j]=='B'){
    sx=i;sy=j;
   }
   if(m[i][j]=='L'){
    gx=i;gy=j;
   }
  }
 }
 int res=bfs();
 printf("%d",res);
 return 0;
}