蓝桥杯：七步诗 ← bfs

【题目来源】
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
*/

【参考文献】
https://www.lanqiao.cn/problems/3447/learning