AcWing 1470. 水桶传递队列
原题链接
简单
作者:
jjj_k
,
2022-03-29 15:55:07
,
所有人可见
,
阅读 133
bfs
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 11, n = 10;
char g[N][N];
queue<PII> q;
PII bg, ed;
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
int d[N][N];
int bfs()
{
q.push({bg.first, bg.second});
d[bg.first][bg.second] = 0;
while(!q.empty())
{
auto t = q.front();
q.pop();
for(int i = 0; i < 4; i++)
{
int x = t.first + dx[i], y = t.second + dy[i];
if(x >= 0 && x < n && y >= 0 && y < n && d[x][y] == -1 && g[x][y] != 'R')
{
d[x][y] = d[t.first][t.second] + 1;
q.push({x, y});
}
}
}
return d[ed.first][ed.second] - 1;
}
int main()
{
memset(d, -1, sizeof d);
for(int i = 0; i < 10; i++)
for(int j = 0; j < 10; j++)
{
cin >> g[i][j];
if(g[i][j] == 'L') bg = {i, j};
if(g[i][j] == 'B') ed = {i, j};
}
cout << bfs();
/*
for(int i = 0; i < 10; i++)
{
for(int j = 0; j < 10; j++)
cout << d[i][j] << ' ';
puts("");
}
*/
return 0;
}