$\color{red}{BFS + 选择性扩散}$
注意点
if(abs(xx - fx) + abs(yy - fy) <= len + 1)
{
len = abs(xx - fx) + abs(yy - fy);
ls.push({xx, yy});
}
/*
这条 if 语句之所以后面是len + 1 而不是 len 是避免出现三个点在同一条线的情况,石头在中间位置。
如果写成 len ,遇到三个点在同一条线情况, 则扩散停止。
*/
差别好像也不大哈
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 20;
char a[N][N];
bool st[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int fx, fy;
int res = 0;
void bfs(int x, int y)
{
queue<PII> ls;
ls.push({x, y});
int len = 0x3f3f;
while(ls.size())
{
int cnt = ls.size();
while(cnt --)
{
int p = ls.front().first, q = ls.front().second;
st[p][q] = true;
ls.pop();
for(int i = 0; i < 4; ++ i)
{
int xx = dx[i] + p, yy = dy[i] + q;
if(a[xx][yy] == 'L') return;
if(xx >= 0 && xx < 10 && yy < 10 && yy >= 0 && !st[xx][yy] && a[xx][yy] != 'R')
{
if(abs(xx - fx) + abs(yy - fy) <= len + 1) //使得寻找具有方向性,朝着最小距离的方向搜索。
{
len = abs(xx - fx) + abs(yy - fy);
ls.push({xx, yy});
}
}
}
}
res ++;
}
}
int main()
{
int x, y;
for(int i = 0; i < 10; ++ i)
for(int j = 0; j < 10; ++ j)
{
cin >> a[i][j];
if(a[i][j] == 'B') x = i, y = j;
else if(a[i][j] == 'L') fx = i, fy = j;
}
bfs(x, y);
cout << res << endl;
}