ROWBOMBING - Editorial

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';
	}
}
1 Like

Solved it using straightforward BFS and using greedy methodology. Without making a new graph.

Basically, do BFS from (1,1) and reach the deepest possible cell.
Then just bomb the next row or the current row (if deepest cell is in the last row), and then restart the bfs using currently bombed row.

End the BFS whenever you reach (n-1, m-1).

This is guranteed to be optimal, because :
Say you are able to reach a cell of row i from a cell of row j .
Then in one move you bomb the next row i+1, you basically can reach any cell of row i+1 in one bombing from row j. Any other way to reach i+1 from j would also require at least 1 bombing (This happens only when we did considered all possible cells to start from, from the jth row.)

Its sorta hard to explain. I guess I suck at explaining . : (

Here’s my accepted code : CodeChef

3 Likes

This is someone’s code which doesn’t use either DFS or BFS. I dont understand it though.
It would be great if someone could explain this .
https://www.codechef.com/viewsolution/77642465

Nice solution. It makes sense to go deepest possible because we want to reach the last row.

It is a better solution

My solution using BFS idea from above: CodeChef

I swear I did the exact same thing! But my code gave me WA