CAPS04-Editorial

PROBLEM LINK:

Practice
Div-2 Contest

Author: [Vivek Kumar Mishra(vkm41101 | CodeChef User Profile for Vivek Kumar Mishra | CodeChef)
Tester: Vivek Kumar Mishra
Editorialist: Harshit Pandey

DIFFICULTY:

HARD

PREREQUISITES:

Graphs

PROBLEM:

Determine whether evacuation of all good people or not.

QUICK EXPLANATION:

We can block all empty neighbouring cells of bad people and then check if all good people can escape and no bad people are able to escape.

EXPLANATION:

Consider all the neighbouring cells of bad people. There shouldn’t be any path from these cells to the cell (n,m). If there is a path from any such cell, the bad person adjacent to that cell can also then reach the cell (n,m). So, if any good and bad people are in adjacent cells, the answer is “No”.

Based on this idea, we can block any empty cell neighbouring a bad person. Suppose there is another solution in which a cell (i,j) neighbouring a bad person does not need to be blocked. There still won’t be any path from (i,j) to (n,m) in that solution. So we can block (i,j) in that solution too without affecting the solution itself.

It is sufficient to block only the empty neighbouring cells of bad people and check the required conditions, which can be done using a bfs on the grid.

Proof:

We will assume there are no adjacent good and bad people since in that case, the answer is “No”. There are three cases:

A bad person is adjacent to the cell (n,m). In this case, the cell (n,m) must be blocked. Now no one will be able to escape. If there is at least one good person present, the answer is “No”.
If after blocking the neighbouring cells of bad people, there is some good person who is not able to escape, then the answer is again “No”.
Otherwise, the answer is always “Yes”. Suppose there is some path from a bad person at cell (i,j) to the cell (n,m). One of the neighbours of this person must be another bad person since the only other case is an adjacent good person (which is already covered above). Extending this, all the cells on the path from (i,j) to (n,m) must have bad people. This is not possible since in this case, there must be a bad person adjacent to (n,m) and this case is already covered above.
Time complexity: O(n⋅m)

SOLUTIONS:

Setter's Solution

#include <bits/stdc++.h>
using namespace std;
#define SIS std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) #define endl ‘\n’ typedeflonglong ll;
#define ll long long
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 55;
char s[MAXN][MAXN];
int dir[4][2] = {{1, 0}, {-1,0}, {0, 1}, {0, -1}};
bool vis[MAXN][MAXN];
int t, n, m, cnt = 0, c1 = 0, c2 = 0;

void dfs(int x, int y)
{
vis[x][y] = true;
if (s[x][y] == ‘#’)
return;
else if(s[x][y] == ‘G’) c1++;
else if(s[x][y] == ‘B’) c2++;
for (
int i = 0; i < 4; i++)
{
int dx = x + dir[i][0];
int dy = y + dir[i][1];
if (dx >= 1 && dy >= 1 && dx <= n && dy <= m && !vis[dx][dy])
dfs(dx, dy);
}
}

int main()
{
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif
cin >> t;
while (t–)
{
memset(vis, false, sizeof(vis));
cnt = c1 = c2 = 0;
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> s[i] + 1;
}
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 dx = i + dir[k][0];
int dy = j + dir[k][1];
if (s[dx][dy] == ‘.’)
s[dx][dy] = ‘#’;
}
}
else if (s[i][j] == ‘G’)
cnt++;
}
}
dfs(n, m);
if (cnt == c1 && c2 == 0)
cout << “Yes” << endl;
else
cout << “No” << endl;
}
return 0;
}