PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: ezdp
Tester: yash_daga
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Finding connected components (DSU or DFS/BFS)
PROBLEM:
You have an N\times N grid, with M of its cells being blocked.
Is it possible to move from (1, 1) to (N, N) with vertical/horizontal moves through only unblocked cells?
EXPLANATION:
We’ll call two blocked cells adjacent if they share an edge or a corner.
In particular, two blocked cells can be diagonally adjacent.
This defines a graph on the blocked cells, with several connected components.
Let’s look at one such connected component.
Suppose it touches both the left and right edges of the grid.
This would then mean that there’s a ‘path’ of blocked cells that stretches from the left end of the grid to the right.
If this were to happen, it’s clear that there’s no way to cross this ‘blocked path’, and since we start at (1, 1) we’ll always stay above it and remain unable to reach (N, N).
In fact, this applies to any blocked path that cuts us off entirely - specifically, one of these four possibilities:
- A path from the left edge to the top edge.
- A path from the left edge to the right edge.
- A path from the bottom edge to the top edge.
- A path from the bottom edge to the right edge.
If any of these four exist, the answer is No; otherwise it’s Yes.
Checking this condition isn’t too hard: create the graph described at the start (which has M vertices and at most 8 edges from each, so is small enough), then check this condition for each connected component of the graph.
Finding connected components can be done quickly using a DSU, or with DFS/BFS.
TIME COMPLEXITY:
\mathcal{O}(M) per testcase.
CODE:
Author's code (C++)
#include<bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define de(x) cout << #x << " = " << x << endl;
using namespace std;
const int MAXN = 1e6 + 6;
const int dx[] = { 0, 0, +1, +1, +1, -1, -1, -1};
const int dy[] = {+1, -1, +1, 0, -1, +1, 0, -1};
template<class T> using matrix = vector<vector<T>>;
bool used[MAXN];
int N, M, IDX, min_x, max_x, min_y, max_y;
matrix<int> G;
map<pair<int, int>, int> blocks;
map<int, pair<int, int>> inv;
void dfs(int u){
used[u] = true;
int x = inv[u].fr, y = inv[u].sc;
min_x = min(min_x, x);
max_x = max(max_x, x);
min_y = min(min_y, y);
max_y = max(max_y, y);
for(auto v : G[u]){
if(used[v]) continue;
dfs(v);
}
}
void s(){
cin >> N >> M;
G = matrix<int>(M + 1);
for(int i = 0; i < M; i ++){
int x, y; cin >> x >> y;
blocks[{x, y}] = ++ IDX;
inv[IDX] = {x, y};
}
for(auto [coord, u] : blocks){
int x = coord.fr, y = coord.sc;
for(int k = 0; k < 8; k ++){
int nx = x + dx[k];
int ny = y + dy[k];
if(blocks.count({nx, ny})){
int v = blocks[{nx, ny}];
G[u].pb(v);
G[v].pb(u);
}
}
}
bool flag = true;
for(int u = 1; u <= IDX; u ++){
if(!used[u]){
min_x = N + 1; max_x = -1;
min_y = N + 1; max_y = -1;
dfs(u);
if((min_x == 1 && max_x == N) ||
(min_y == 1 && max_y == N) ||
(min_x == 1 && min_y == 1) ||
(max_x == N && max_y == N))
flag = false;
}
}
cout << (flag ? "YES" : "NO") << endl;
for(int u = 1; u <= IDX; u ++){
used[u] = false;
}
blocks.clear();
inv.clear();
IDX = 0;
}
int main(){
int t; cin >> t; while(t --) s();
}
Tester's code (C++)
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+5;
int par[N], siz[N], mi_x[N], mx_x[N], mi_y[N], mx_y[N];
int findset(int a)
{
if(par[a]==a)
return a;
return par[a]=findset(par[a]);
}
void unionset(int a, int b)
{
a=findset(a);
b=findset(b);
if(a==b)
return;
if(siz[a]>siz[b])
swap(a, b);
par[a]=b;
siz[b]+=siz[a];
mi_x[b]=min(mi_x[b], mi_x[a]);
mi_y[b]=min(mi_y[b], mi_y[a]);
mx_x[b]=max(mx_x[b], mx_x[a]);
mx_y[b]=max(mx_y[b], mx_y[a]);
}
int dx[]={1, 1, 1, -1, -1, -1, 0, 0};
int dy[]={1, -1, 0, 1, -1, 0, 1, -1};
int32_t main()
{
int t;
cin>>t;
while(t--)
{
int n, m;
cin>>n>>m;
int id=1;
map <pair <int, int>, int> mp;
for(int i=0;i<m;i++)
{
int x, y;
cin>>x>>y;
mp[{x, y}]=id;
par[id]=id;
siz[id]=1;
mx_x[id]=mi_x[id]=x;
mx_y[id]=mi_y[id]=y;
id++;
}
for(auto [pt, id]:mp)
{
for(int d=0;d<8;d++)
{
int nx=pt.first+dx[d], ny=pt.second+dy[d];
if(mp.find({nx, ny})!=mp.end())
unionset(id, mp[{nx, ny}]);
}
}
int f=0;
for(auto [pt, id]:mp)
{
if(mi_x[id]==1 && mx_x[id]==n)
f=1;
if(mi_y[id]==1 && mx_y[id]==n)
f=1;
if(mi_x[id]==1 && mi_y[id]==1)
f=1;
if(mx_x[id]==n && mx_y[id]==n)
f=1;
}
cout<<(f ? "NO\n" : "YES\n");
}
}
Editorialist's code (Python)
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
def find(self, a):
acopy = a
while a != self.parent[a]:
a = self.parent[a]
while acopy != a:
self.parent[acopy], acopy = a, self.parent[acopy]
return a
def union(self, a, b):
self.parent[self.find(b)] = self.find(a)
import itertools
for _ in range(int(input())):
n, m = map(int, input().split())
id = dict()
marked = []
for i in range(m):
x, y = map(int, input().split())
marked.append((x, y))
id[(x, y)] = i+2
dsu = UnionFind(m+2)
for i, (x, y) in enumerate(marked):
for dx, dy in itertools.product([-1, 0, 1], repeat=2):
X, Y = x+dx, y+dy
if (X, Y) in id: dsu.union(i+2, id[(X, Y)])
if x == n or y == 1: dsu.union(i+2, 0)
if x == 1 or y == n: dsu.union(i+2, 1)
print('No' if dsu.find(0) == dsu.find(1) else 'Yes')