常见的网站推广途径,网站建设原则包括哪些内容,绘图软件,外链的作用【题目来源】https://www.lanqiao.cn/problems/3447/learning/【题目描述】 煮豆燃豆苴#xff0c;豆在釜中泣。本是同根生#xff0c;相煎何太急?---曹植 所以#xff0c;这道题目关乎豆子! 话说赤壁之战结束后#xff0c;曹操的船舰被刘备烧了#xff0c;引领军队从华容…【题目来源】https://www.lanqiao.cn/problems/3447/learning/【题目描述】 煮豆燃豆苴豆在釜中泣。本是同根生相煎何太急?---曹植 所以这道题目关乎豆子! 话说赤壁之战结束后曹操的船舰被刘备烧了引领军队从华容道撤退路上遇到了泥泞道路不通畅又刮起了大风没办法只好让羸弱的士兵背着草填在马下骑兵才能过去。 走着走着军队路遇—片豆地由于战马已经饥饿难耐急需吃些豆子补充体力这样才能继续行进但是大家都知道马儿只会走“日”字于是问题来了已知豆地的大小为 n×mn 行 m 列每个坐标点上面有散落着的豆子、枯萎的豆萁以及坑洼的湿地马儿只会吃豆子不会吃豆萁且马儿不会走到坑洼的湿地上面因为湿地会让它深陷其中无法行动当然也不能走到 n ×m 豆地范围之外。 为了方便描述豆子用字母 b 表示豆萁用字母 q 表示湿地用字母 x 表示马儿所在的位置用字母S表示题目测试数据保证 S 在 n×m 的豆地范围内)现在请你计算—下马儿最多能吃到豆地里面多少颗豆子并输出对应的答案。【输入格式】 输入第 1 行包含两个正整数 n 和 m表示豆地的大小。 第 2n1 行每行包含 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【算法代码】
#includebits/stdc.h
using namespace std;typedef pairint,int PII;const int maxn404;
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};queuePII Q;
int bfs(int x,int y) {int ans0;Q.push({x,y});while(Q.size()) {PII tQ.front();int xt.first;int yt.second;Q.pop();for(int i0; i8; i) {int nxxdx[i];int nyydy[i];if(nx0 nxn ny0 nym (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() {cinnm;char ch;for(int i0; in; i) {for(int j0; jm; j) {cinch;if(chb) st[i][j]0;else if(chq) st[i][j]-1;else if(chS) sxi,syj;else st[i][j]1;}}st[sx][sy]1;coutbfs(sx,sy);return 0;
}/*
in1:
2 3
Sqx
xxxout1:
0
---------
in2:
3 3
bbb
Sqb
bbbout2:
7
*/
【参考文献】https://www.lanqiao.cn/problems/3447/learning
