【Codeforces Round #648 (Div. 2) D】Solve The Maze
The Codeforces div round Solve
2023-09-14 09:03:41 时间
题目链接
翻译
让所有的好人都能到(n,m)。所有的坏人都不能到(n,m)。
墙不能走,空格可以改为放墙。
问你可不可能。
题解
只要把坏人相邻的四个格子考虑一下,为空格的放成墙即可。
考虑被换成墙的空格,如果其他好人要通过这个墙才能到达终点,那么这个坏人也能跟着到达终点。无解。
所以不会对其他好人到终点造成影响。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 50;
const int dx[4] = {0,0,1,-1};
const int dy[4] = {1,-1,0,0};
int T,n,m;
char s[N+10][N+10];
int cntG,cntB;
void dfs(int x,int y){
if (s[x][y] == '#'){
return;
}
if (s[x][y] == 'B'){
cntB++;
}
if (s[x][y] == 'G'){
cntG++;
}
s[x][y] = '#';
for (int i = 0;i < 4; i++){
int tx = x + dx[i],ty = y + dy[i];
if (tx >= 1 && tx <= n && ty >= 1 && ty <= m){
dfs(tx,ty);
}
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin >> T;
while(T--){
cin >> n >> m;
for (int i = 1;i <= n; i++){
cin >> (s[i]+1);
}
int initG = 0;
for (int i = 1;i <= n; i++){
for (int j = 1;j <= m; j++){
if (s[i][j] == 'B'){
for (int k = 0;k < 4; k++){
int ti = i + dx[k], tj = j + dy[k];
if (ti >= 1 && ti <= n && tj >= 1 && tj <= m){
if (s[ti][tj] == '.'){
s[ti][tj] = '#';
}
}
}
}else if (s[i][j] == 'G'){
initG++;
}
}
}
cntG = 0,cntB = 0;
dfs(n,m);
if (cntG!=initG || cntB >0){
cout <<"NO"<<endl;
}else{
cout <<"YES"<<endl;
}
}
return 0;
}
相关文章
- ORA-26856: STREAMS string has insufficient database privilege to access the queue. ORACLE 报错 故障修复 远程处理
- ORA-28340: a different encryption algorithm has been chosen for the table ORACLE 报错 故障修复 远程处理
- ORA-29932: the type being dropped is a statistics type ORACLE 报错 故障修复 远程处理
- ORA-31122: The string operator has incorrect RHS value ORACLE 报错 故障修复 远程处理
- ORA-38454: attribute set not defined for the column being indexed ORACLE 报错 故障修复 远程处理
- ORA-38852: cannot mark the current instance (redo thread) as disabled ORACLE 报错 故障修复 远程处理
- ORA-39774: parse of metadata stream failed with the following error: string ORACLE 报错 故障修复 远程处理
- ORA-41104: The database: string is the Cluster Director. ORACLE 报错 故障修复 远程处理
- ORA-48408: The incident number exceeds the maximum number [string] ORACLE 报错 故障修复 远程处理
- ORA-48409: The ADR homes exceeds the maximum number [string] ORACLE 报错 故障修复 远程处理
- ORA-48412: The parameters exceeds the maximum number [string] ORACLE 报错 故障修复 远程处理
- ORA-53253: The metadata for the new DICOM object is invalid. ORACLE 报错 故障修复 远程处理
- ORA-06421: NETCMN: Error detected in the read-in data ORACLE 报错 故障修复 远程处理
- ORA-13638: The user interrupted the current operation. ORACLE 报错 故障修复 远程处理
- ORA-18120: XUDY0021 – The result XDM instance violates XDM constraints ORACLE 报错 故障修复 远程处理
- MySQL 5.7.17:The Latest Upgrade of the Database System(mysql5.7.17)
- 注册Oracle数据库,Unlock the Power(oracle注册数据库)
- Understanding the Basics of Linux Blocks for File Management.(linuxblocks)