【题目来源】
https://www.lanqiao.cn/problems/3447/learning/
【题目描述】
煮豆燃豆苴，豆在釜中泣。本是同根生，相煎何太急?---曹植
所以，这道题目关乎豆子!
话说赤壁之战结束后，曹操的船舰被刘备烧了，引领军队从华容道撤退，路上遇到了泥泞，道路不通畅，又刮起了大风，没办法，只好让羸弱的士兵背着草填在马下，骑兵才能过去。
走着走着，军队路遇—片豆地，由于战马已经饥饿难耐，急需吃些豆子补充体力，这样才能继续行进，但是大家都知道，马儿只会走“日”字，于是问题来了，已知豆地的大小为 n×m（n 行 m 列），每个坐标点上面有散落着的豆子、枯萎的豆萁以及坑洼的湿地，马儿只会吃豆子，不会吃豆萁，且马儿不会走到坑洼的湿地上面，因为湿地会让它深陷其中，无法行动；当然也不能走到 n ×m 豆地范围之外。
为了方便描述，豆子用字母 b 表示，豆萁用字母 q 表示，湿地用字母 x 表示，马儿所在的位置用字母S表示（题目测试数据保证 S 在 n×m 的豆地范围内)，现在请你计算—下，马儿最多能吃到豆地里面多少颗豆子，并输出对应的答案。
【输入格式】
输入第 1 行包含两个正整数 n 和 m，表示豆地的大小。
第 2～n+1 行每行包含 m 个字符，表示豆地里面的豆子、豆萁、湿地以及马儿所在的起点位置。
【输出格式】
输出—行，这—行包含一个整数，表示答案。
【样例输入1】
2 3
Sqx
xxx
【输出样例1】
0
【输入样例2】
3 3
bbb
Sqb
bbb
【输出样例2】
7
【说明/提示】
对于所有评测数据，1≤n, m≤400。
【算法分析】
BFS算法助记：建-入-量：头-出-入，详见：
https://blog.csdn.net/hnjzsyjyj/article/details/125801217
【算法代码】
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int maxn=404;
int st[maxn][maxn];
int n,m;
int sx,sy;
int dx[]= {-2,-1,1,2,2,1,-1,-2};
int dy[]= {1,2,2,1,-1,-2,-2,-1};
queue<PII> Q;
int bfs(int x,int y) {
int ans=0;
Q.push({x,y});
while(Q.size()) {
PII t=Q.front();
int x=t.first;
int y=t.second;
Q.pop();
for(int i=0; i<8; i++) {
int nx=x+dx[i];
int ny=y+dy[i];
if(nx>=0 && nx<n && ny>=0 && ny<m && (st[nx][ny]==0 || st[nx][ny]==-1)) {
if(st[nx][ny]==0) ans++;
st[nx][ny]=1;
Q.push({nx,ny});
}
}
}
return ans;
}
int main() {
cin>>n>>m;
char ch;
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
cin>>ch;
if(ch=='b') st[i][j]=0;
else if(ch=='q') st[i][j]=-1;
else if(ch=='S') sx=i,sy=j;
else st[i][j]=1;
}
}
st[sx][sy]=1;
cout<<bfs(sx,sy);
return 0;
}
/*
in1:
2 3
Sqx
xxx
out1:
0
---------
in2:
3 3
bbb
Sqb
bbb
out2:
7
*/
