锐客网

  1. 首页 > it技术 > >

#|D. Solve The Maze（思维+bfs）Codeforces Round #648 (Div. 2)

#cf

原题链接： https://codeforces.com/problemset/problem/1365/D
#|D. Solve The Maze（思维+bfs）Codeforces Round #648 (Div. 2)
文章图片

测试样例：

【#|D. Solve The Maze（思维+bfs）Codeforces Round #648 (Div. 2)】输入
6
1 1
.
1 2
G.
2 2
#B
G.
2 3
G.#
B#.
3 3
#B.
#…
GG.
2 2
#B
B.
输出
Yes
Yes
No
No
Yes
Yes
样例解释
对于第一个和第二个测试用例，所有条件都已经满足。
对于第三个测试用例，只有1个空单元(2，2)，如果将他墙化那么在(1，2)处的好人将无法逃跑出来。
对于第四个测试案例，(1，1)的好人无法逃脱。
对于第五个测试用例，Vivek可以墙化单元格(2，3)和(2，2)。
对于最后一个测试用例，Vivek可以墙化目标单元格(2，2)。
题意： 给你一个迷宫，你可以将空单元变墙。要求你判断好人能不能全部出来，坏人能不能都困在迷宫。
解题思路： 什么问题我们都要清楚问题的本意。这个题目是要让所有的好人全部出来，所有的坏人都困在迷宫，我们试想，如果要让坏人困在迷宫，那么我们就必须将它的四周都变成墙使得它绝对困在这里不能出去。这样处理之后是能达到目的的，如果不这样，好人途径了坏人的四周或者就在坏人的四周，那么坏人不就可以跟着好人走了吗？还有一种特殊情况，如果迷宫出口的上边和左边有坏人，那这也是不可能的。经过这个处理之后我们就可以杜绝坏人出去迷宫，对几种情况特判得出结果。之后，我们就是要判断所有好人能不能出来。如果我们以好人为第一角色开启bfs，那这是非常慢的，每一个好人都要进行一次。我们换种思考，如果我以迷宫出口为第一角色开启搜索，如果路线上能够遇到所有好人，那好人到迷宫出口就有路径，这样，我们的任务不就简单了吗？OK，具体看代码。
AC代码：
/* *邮箱：unique_powerhouse@qq.com *blog:https://me.csdn.net/hzf0701 *注：文章若有任何问题请私信我或评论区留言，谢谢支持。 * */ #include //POJ不支持#define rep(i,a,n) for (int i=a; i<=n; i++)//i为循环变量，a为初始值，n为界限值，递增 #define per(i,a,n) for (int i=a; i>=n; i--)//i为循环变量， a为初始值，n为界限值，递减。 #define pb push_back #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0) #define fi first #define se second #define mp make_pairusing namespace std; const int inf = 0x3f3f3f3f; //无穷大 const int maxn = 1e2; //最大值。 typedef long long ll; typedef long double ld; typedef pairpll; typedef pair pii; //*******************************分割线，以上为自定义代码模板***************************************//int t,n,m,flag,cnt1,cnt2; //t组测试样例，n*m的大小关系,flag判断可不可行。cnt1统计好人数，cnt2统计可以到达迷宫出口的好人数。 char maze[maxn][maxn]; //迷宫 bool vis[maxn][maxn]; int go[4][2]={{1,0},{0,1},{0,-1},{-1,0}}; bool change(){ bool flag=true; rep(i,0,n-1){ rep(j,0,m-1){ if(maze[i][j]=='B'){ if(i>0){ if(maze[i-1][j]=='.'){ maze[i-1][j]='#'; } else if(maze[i-1][j]=='G'){ flag=false; break; } } if(j>0){ if(maze[i][j-1]=='.'){ maze[i][j-1]='#'; } else if(maze[i][j-1]=='G'){ flag=false; break; } } if(i=n||j>=m) return false; if(maze[i][j]=='#') return false; if(vis[i][j]) return false; return true; } int bfs(){ memset(vis,false,sizeof(vis)); int sum=0; vis[n-1][m-1]=true; queue q; q.push(mp(n-1,m-1)); pii temp1,head; while(!q.empty()){ head=q.front(); q.pop(); rep(i,0,3){ temp1.fi=head.fi+go[i][0]; temp1.se=head.se+go[i][1]; if(check(temp1.fi,temp1.se)){ if(maze[temp1.fi][temp1.se]=='G') sum++; vis[temp1.fi][temp1.se]=true; q.push(temp1); } } } return sum; } int main(){ //freopen("in.txt", "r", stdin); //提交的时候要注释掉 IOS; while(cin>>t){ while(t--){ cin>>n>>m; cnt2=0; rep(i,0,n-1){ cin>>maze[i]; rep(j,0,m-1){ if(maze[i][j]=='G') cnt2++; } } if(!change()){ cout<<"NO"<

    推荐阅读


    上一篇：1024，祝所有程序员节日快乐

    下一篇：安卓开发|自定义Android属性动画框架