题目传送门
分析： 题目要求为让所有B无法到达右下角，所有G都能到达右下角，很容易想到将所有的B周围的’.'换掉（这是花费最小，也就是让好人G有最多的路可走的计策）再检测条件就ok，检测的时候有个技巧，那就是从终点出发，检查所有能到的位置（单个终点或起点的问题就这么搞，会节省很多时间）
错误原因： 比赛的时候认为将B周围的 ‘.’ 换掉，B就一定不能到右下角了，漏掉了B与G相邻的情况（相邻则G能到B也能到，必然无解）。改了之后发现还是wrong answer，结果是dfs写错了（我的深广搜就学的这么烂吗?）。这个dfs就是Lake counting问题，参考着写就没问题了 那么简单的都写不对,还记忆化搜索，淦
其实用广搜更合理…
大致证明一下思路： 如果B周围的某一个 ‘.’ 可达右下角，那么在这里将’.'换掉是最佳的选择（给G留出最多的路），如果不可以到达，换掉也无妨，换不换B走这里都出不来，G也是，G必然不会走这里来。
【BFS|Solve The Maze（codeforces）】最后的代码：
#include
#include
using namespace std;
const int MAX_N=51;
char maze[MAX_N][MAX_N];
int Next[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
int n,m,good,bad;
void tu(int x,int y)
{
for(int i=0;
i<4;
i++)
{
int nx=x+Next[i][0],ny=y+Next[i][1];
if(nx=0&&ny=0&&maze[nx][ny]=='.')maze[nx][ny]='#';
}
}
void dfs(int x,int y)
{
if(maze[x][y]=='#')return ;
if(maze[x][y]=='G')good--;
//能到就将好人个数减一，减为0时才满足条件
if(maze[x][y]=='B')bad++;
//但凡有一个坏人，都不满足条件
maze[x][y]='#';
for(int i=0;
i<4;
i++)
{
int nx=x+Next[i][0],ny=y+Next[i][1];
if(nx=0&&ny=0&&maze[nx][ny]!='#')dfs(nx,ny);
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>n>>m;
for(int i=0;
i>maze[i][j];
for(int i=0;
i 推荐阅读
- 遇见蓝桥遇见你|小唐开始刷蓝桥（一）2020年第十一届C/C++ B组第二场蓝桥杯省赛真题
- DFS|使用DFS（深搜）遍历所有的序列所有的子组合（子序列）（排列组合中的组合）
- Pavel loves grid mazes（CodeForce 377A）
- DFS|CodeForces - 275B （广搜）
- 搜索|Wannafly模拟赛3-B 贝伦卡斯泰露（DFS）
- CodeForces|2018.1.27【CodeForces - 689B】解题报告（BFS）
- CodeForces 377A
- DFS|CodeForces - 1099D（树上贪心+DFS）
- Codeforces Round #336 (Div. 1) D. Power Tree