PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: grayhathacker
Tester: kaori1
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
PROBLEM:
A prison is represented by a N\times M grid filled with 0's and 1's, being prisoners and guards respectively.
A prisoner can move one step in any of the four directions.
What’s the minimum number of guards any prisoner has to cross to exit the prison?
EXPLANATION:
From the perspective of a single prisoner, things are pretty straightforward: you start at some cell, can move in one of four directions, and each movement has a ‘weight’ - either 0 or 1 depending on whether you end up in a cell with another prisoner or a guard.
You want, of course, to reach the border of the grid.
This screams “shortest path”, and indeed, can be solved quickly using one of several shortest path algorithms: Dijkstra’s algorithm being the standard, but you can also save a log factor and use 0-1 bfs, since the weights are all 0 or 1.
The obvious issue with doing this is that it’s fast enough for a single prisoner (being \mathcal{O}(NM) or \mathcal{O}(NM\log{(NM)}) depending on the chosen algorithm), but having to run this for every prisoner makes it quite slow.
However, observe that no matter what the starting point is, a couple of things remain the same: the underlying graph doesn’t change, and neither does the destination (being the borders of the grid).
So, we really have a case of “multiple sources, single destination”. That’s easily taken care of - just reverse the process!
That is, start the search at the destination, the grid borders - and compute the shortest distance from there to every other cell in the grid (which is what the single-source shortest path algorithms do anyway).
To deal with the fact that the grid borders aren’t a single point, there are a couple of ways: the simplest is to just pretend the grid is surrounded by a bunch of 0's, and choose any one of them as the starting point for the search.
Alternately, you can start the search by first putting all the cells on the grid border into your queue/priority queue and assigning them a weight of 0 (instead of starting with a single cell, as usual). This is what is commonly known as multisource Dijkstra (or BFS/DFS/whatever).
TIME COMPLEXITY:
\mathcal{O}(NM) per testcase.
CODE:
Author's code (C++)
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n,m;
cin>>n>>m;
string a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
vector<vector<int>> d( n , vector<int> (m, INT_MAX));
deque<pair<int, int>> q;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(i==0 || j==0 || i==n-1 || j==m-1)
{
d[i][j]=a[i][j]-'0';
if(a[i][j]=='0')
q.push_front({i,j});
else
q.push_back({i,j});
}
}
}
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
while (!q.empty()) {
pair<int,int> cur = q.front();
int x = cur.first;
int y = cur.second;
q.pop_front();
for(int i=0;i<4;i++)
{
int adj_x = x+dx[i];
int adj_y = y+dy[i];
if(adj_x<0 || adj_x>=n || adj_y<0 || adj_y>=m)
continue;
int weight = a[adj_x][adj_y]-'0';
if (d[x][y] + weight < d[adj_x][adj_y]) {
d[adj_x][adj_y] = d[x][y] + weight;
if (weight == 1)
q.push_back({adj_x,adj_y});
else
q.push_front({adj_x,adj_y});
}
}
}
int ans=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
if(a[i][j]=='0')
ans=max(ans, d[i][j]);
}
cout<<ans<<"\n";
}
}
Tester's code (C++)
#include<bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) static_cast<int>((x).size())
#define int long long
typedef long long ll;
vector<array<int, 2>> dxy = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
string s[n];
for (int i = 0; i < n; i++) cin >> s[i];
int d[n][m];
priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> pq;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
d[i][j] = n + m + 100;
if (i == 0 || j == 0 || i == n - 1 || j == m - 1) {
if (s[i][j] == '1') d[i][j] = 1;
else d[i][j] = 0;
pq.push({d[i][j], i, j});
}
}
}
while (sz(pq)) {
auto [di, x, y] = pq.top();
pq.pop();
if (di != d[x][y]) continue;
for (auto [dx, dy] : dxy) {
int nx = x + dx, ny = y + dy;
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
int nd = di + (s[nx][ny] == '1');
if (d[nx][ny] <= nd) continue;
d[nx][ny] = nd;
pq.push({nd, nx, ny});
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (s[i][j] == '0') ans = max(ans, d[i][j]);
}
}
cout << ans << "\n";
}
}
