PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Jeevan Jyot Singh
Testers: Tejas Pandey, Hriday
Editorialist: Nishank Suresh
DIFFICULTY:
TBD
PREREQUISITES:
Single-source shortest path
PROBLEM:
You have an N\times M grid, each cell of which is either blocked or empty. You can travel only between empty cells.
In one move, you can pick any row and unblock all of its cells. Find the minimum number of moves needed so that (N, M) is reachable from (1, 1).
EXPLANATION:
Let’s think of the grid as a graph: each cell (i, j) is a vertex, and from (i,j) you can move to the 4 cells \{(i-1, j), (i+1,j), (i, j+1), (i, j-1)\} (if they exist and are empty).
However, this isn’t enough information to represent everything we need. In particular, to know whether it’s possible to move to another vertex or not, we need two pieces of information:
- Was that cell originally empty?
- If not, has a row bombing operation been performed on its row?
Our graph formulation doesn’t encapsulate information about the second point at all, so we need to augment it a bit.
Instead of N\times M vertices, let’s consider a graph on 2\times N\times M vertices, where
- (i, j, 0) represents cell (i, j) such that a row-bombing operation has not been performed on row i.
- (i, j, 1) represents cell (i, j) such that a row-bombing operation has been performed on row i.
Note that edges now have to be created appropriately when considering the third state, which is a bit of casework.
Details
Consider (i, j, 0). From here, we can move to:
- Any of its 4 neighbors mentioned above, in the 0 state, if the corresponding cell was initially empty
- (i, j, 1) by bombing this row
- (i-1, j, 1) and (i+1, j, 1) by bombing the row above/below respectively to clear them out
Similarly, (i, j,1) can move to:
- (i, j+1, 1) and (i,j-1, 1) freely, since the row has been bombed
- (i-1, j, 0) and (i+1, j, 0) if the corresponding cells were initially empty
- (i-1, j, 1) and (i+1, j, 1) by bombing the corresponding rows
This gives us a graph with \mathcal{O}(N\cdot M) vertices and edges.
Note that we somehow want to reach (N, M) from (1, 1) in this graph, while minimizing the number of bombings.
Under our construction, a bombing is performed exactly when we move from a state (i_1, j_1, 0) to a state (i_2, j_2,1), i.e, a 0-state to a 1-state.
So, let’s weight our graph: every edge from a 0-state to 1-state has weight 1, while every other edge has weight 0.
The answer is then simply the shortest path in this weighted graph from (1, 1, 0) to either (N, M, 0) or (N, M, 1).
This can be computed using Dijkstra’s algorithm, of course. However, since the edge weights are only 0 and 1, it’s possible to solve the problem in linear time using 0-1 bfs.
TIME COMPLEXITY
\mathcal{O}(N\cdot M) per test case.
CODE:
Preparer's code (C++)
/**
* the_hyp0cr1t3
* 18.10.2022 18:59:48
**/
#ifdef W
#include <k_II.h>
#else
#include <bits/stdc++.h>
using namespace std;
#endif
// -------------------- Input Checker Start --------------------
long long readInt(long long l, long long r, char endd)
{
long long x = 0;
int cnt = 0, fi = -1;
bool is_neg = false;
while(true)
{
char g = getchar();
if(g == '-')
{
assert(fi == -1);
is_neg = true;
continue;
}
if('0' <= g && g <= '9')
{
x *= 10;
x += g - '0';
if(cnt == 0)
fi = g - '0';
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);
assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
}
else if(g == endd)
{
if(is_neg)
x = -x;
if(!(l <= x && x <= r))
{
cerr << "L: " << l << ", R: " << r << ", Value Found: " << x << '\n';
assert(false);
}
return x;
}
else
{
assert(false);
}
}
}
string readString(int l, int r, char endd)
{
string ret = "";
int cnt = 0;
while(true)
{
char g = getchar();
assert(g != -1);
if(g == endd)
break;
cnt++;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
long long readIntSp(long long l, long long r) { return readInt(l, r, ' '); }
long long readIntLn(long long l, long long r) { return readInt(l, r, '\n'); }
string readStringSp(int l, int r) { return readString(l, r, ' '); }
string readStringLn(int l, int r) { return readString(l, r, '\n'); }
void readEOF() { assert(getchar() == EOF); }
vector<int> readVectorInt(int n, long long l, long long r)
{
vector<int> a(n);
for(int i = 0; i < n - 1; i++)
a[i] = readIntSp(l, r);
a[n - 1] = readIntLn(l, r);
return a;
}
// -------------------- Input Checker End --------------------
const pair<int, int> dirs[] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
const int INF = 1e9;
auto chmax = [](auto& A, auto&& B) { return B > A? A = B, true : false; };
auto chmin = [](auto& A, auto&& B) { return B < A? A = B, true : false; };
auto intended(int N, int M, vector<string> s) {
vector d(N, vector<vector<int>>(M, vector<int>(2, INF)));
deque<tuple<int, int, int, int>> q;
q.emplace_back(0, 0, 0, 0); d[0][0][0] = 0;
while(!q.empty()) {
auto [x, y, o, dist] = q.front(); q.pop_front();
if(d[x][y][o] < dist) continue;
if(chmin(d[x][y][1], dist + 1))
q.emplace_back(x, y, 1, dist + 1);
for(auto [dx, dy]: dirs) {
int nx = x + dx;
int ny = y + dy;
if(!(0 <= nx and nx < N and 0 <= ny and ny < M)) continue;
if(dx == 0) {
if(s[nx][ny] == '.' or o == 1) {
if(chmin(d[nx][ny][o], dist))
q.emplace_front(nx, ny, o, dist);
} else {
if(chmin(d[nx][ny][1], dist + 1))
q.emplace_back(nx, ny, 1, dist + 1);
}
} else {
if(s[nx][ny] == '.') {
if(chmin(d[nx][ny][0], dist))
q.emplace_front(nx, ny, 0, dist);
} else {
if(chmin(d[nx][ny][1], dist + 1))
q.emplace_back(nx, ny, 1, dist + 1);
}
}
}
}
return min(d[N - 1][M - 1][0], d[N - 1][M - 1][1]);
}
int main() {
#if __cplusplus > 201703L
namespace R = ranges;
#endif
ios_base::sync_with_stdio(false), cin.tie(nullptr);
int64_t sum_n = 0;
int tests = readIntLn(1, 2e5);
while(tests--) [&] {
int N = readIntSp(1, 2e5);
int M = readIntLn(1, 2e5);
assert(1LL * N * M <= 5e5);
sum_n += 1LL * N * M;
assert(sum_n <= 5e5);
vector<string> s(N);
for(auto &x: s) {
x = readStringLn(M, M);
assert(count(x.begin(), x.end(), '.') + count(x.begin(), x.end(), '#') == M);
}
cout << intended(N, M, s) << '\n';
}();
cerr << sum_n << '\n';
#ifndef W
readEOF();
#endif
} // ~W
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
int sm = 0;
while(t--) {
int n, m;
cin >> n >> m;
assert(n * m <= 500000);
sm += (n * m);
assert(sm <= 500000);
char c[n][m];
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++) {
cin >> c[i][j];
assert(c[i][j] == '.' || c[i][j] == '#');
}
assert(c[0][0] == '.');
priority_queue<pair<int, pair<int, int>>> pq;
pq.push({0, {0, 0}});
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int vis[n][m];
memset(vis, -1, sizeof(vis));
vis[0][0] = 0;
int ans = 0;
int vr[n];
memset(vr, 0, sizeof(vr));
while(!pq.empty()) {
int nx = pq.top().second.first;
int ny = pq.top().second.second;
int dis = -pq.top().first;
pq.pop();
if(nx == n - 1 && ny == m - 1) {
ans = dis;
break;
}
if(dis > vis[nx][ny]) continue;
for(int i = 0; i < 4; i++) {
int mx = nx + dx[i];
int my = ny + dy[i];
if(mx > -1 && mx < n && my > -1 && my < m) {
if(c[mx][my] == '#') {
if(!vr[mx]) {
vr[mx] = 1;
for(int k = 0; k < m; k++)
if(vis[mx][k] == -1 || vis[mx][k] > dis + 1)
pq.push({-(dis + 1), {mx, k}}), vis[mx][k] = dis + 1;
}
}
else if(vis[mx][my] == -1 || vis[mx][my] > dis)
pq.push({-dis, {mx, my}}), vis[mx][my] = dis;
}
}
}
cout << ans << "\n";
}
return 0;
}
Editorialist's code (C++)
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n, m; cin >> n >> m;
vector<string> grid(n);
for (int i = 1; i <= n; ++i) {
cin >> grid[i-1];
}
const int inf = 1e9;
vector<vector<array<int, 2>>> dist(n, vector(m, array{inf, inf}));
dist[0][0][0] = 0;
deque<array<int, 3>> dq = {{0, 0, 0}};
vector<array<int, 2>> dir = {{0,1}, {1, 0}, {-1, 0}, {0, -1}};
auto upd = [&] (int x, int y, int lv, int d) {
if (dist[x][y][lv] > d) {
dist[x][y][lv] = d;
dq.push_front({x, y, lv});
}
};
while (!dq.empty()) {
auto [x, y, lv] = dq.front(); dq.pop_front();
int d = dist[x][y][lv];
for (auto [dx, dy] : dir) {
int nx = x + dx, ny = y + dy;
if (nx < 0 or nx >= n or ny < 0 or ny >= m) continue;
if (nx == x and (lv == 1 or grid[nx][ny] == '.')) upd(nx, ny, lv, d);
else if (nx != x and grid[nx][ny] == '.') upd(nx, ny, 0, d);
}
for (int dx : {-1, 0, 1}) {
if (x+dx < 0 or x+dx >= n) continue;
if (dist[x+dx][y][1] > 1 + d) {
dist[x+dx][y][1] = 1 + d;
dq.push_back({x+dx, y, 1});
}
}
}
cout << min(dist[n-1][m-1][0], dist[n-1][m-1][1]) << '\n';
}
}