PROBLEM LINK:
Author: Praveen Dhinwa
Tester: Hasan Jaddouh
Editorialist: Sidhant Bansal
DIFFICULTY -
Easy - Medium
PREREQUISITES -
BFS
PROBLEM -
Given a grid of n * m dimension, where the value of cell (i, j) is a[i][j].
Determine the minimum no. of moves after which all the values of array a[][] will be equal given that in every move for every cell (i, j) its value a[i][j] becomes the maximum of the 8 adjacent values to that cell, only if this maximum value is greater than current a[i][j].
EXPLANATION -
Firstly, we can easily see that this process will end when all the values in the a[][] array have attained the maximum element of the a[][] array.
Now if we find the maximum element in the a[][] array and mark all its occurrences as SPECIAL.
The problem is reduced to this -
For each cell (i, j) we need to determine the shortest distance from cell (i, j) to any cell which is marked as SPECIAL, and the maximum of all these shortest distances is our answer. This can be done using a multi - source BFS.
This works because the shortest distance for cell (i, j) is equal to the no. of moves taken for the max value to reach cell (i, j).
Graph Theory Equivalent -
The graph theory equivalent to the above problem is this -
Given a graph with X nodes and Y edges where all the edges are bidirectional and have weight 1. Also where Z of its nodes are marked SPECIAL. Find the shortest distance of each node from any of the SPECIAL node, meaning that you have to minimise the shortest distance given that one end point is fixed as the current node and the other end point can be any SPECIAL node.
The naive method to do the above problem is to do a BFS from each SPECIAL node and then for each node determine which SPECIAL node is optimal for it depending on which SPECIAL node is nearest to it. But this solution is of the order O((X + Y) * Z), which will TLE in our case.
The faster method is to assume a fictional node W and assume that it is connected all the Z SPECIAL nodes with weight 1. Now a single BFS considering the source as W will give the answer with an extra 1 added. So subtract 1 from the shortest distances since the edge from W to the SPECIAL nodes is irrelevant. This method is commonly known as multi - source BFS as it enables us to have multiple sources. Same method can be extended to Dijkstra algorithm. This solution is fast enough and is of the order O(X + Y).
Below is a C++ implementation for better understanding -
#include "bits/stdc++.h"
using namespace std;
const int N = 505;
int a[N][N];
int dx[] = {1, 1, 1, -1, -1, -1, 0, 0}, dy[] = {1, 0, -1, 1, 0, -1, 1, -1};
bool visited[N][N];
queue<pair<pair<int, int>, int> > Q;
int n, m;
bool valid(int x, int y){
if(x < 1 or x > n or y < 1 or y > m) return false;
else return true;
}
void solve(){
int maxm = 0;
cin>>n>>m;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin>>a[i][j];
maxm = max(maxm, a[i][j]);
visited[i][j] = 0;
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(a[i][j] == maxm){
Q.push({{i, j}, 0});
visited[i][j] = 1;
}
}
}
int ans = 0;
while(!Q.empty()){
int x = Q.front().first.first, y = Q.front().first.second, d = Q.front().second;
ans = max(ans, d);
Q.pop();
for(int i = 0; i < 8; i++){
if(valid(x + dx[i], y + dy[i]) == 1 and visited[x + dx[i]][y + dy[i]] == 0){
Q.push({{x + dx[i], y + dy[i]}, d + 1});
visited[x + dx[i]][y + dy[i]] = 1;
}
}
}
cout<<ans<<endl;
}
int main(){
int t;
scanf("%d", &t);
while(t--) solve();
}
Complexity -
The time complexity of a single BFS is O(no. of vertices + no. of edges in the graph) = O(n * m)
