### 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*[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*[j] becomes the maximum of the 8 adjacent values to that cell, only if this maximum value is greater than current a*[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*[j];
maxm = max(maxm, a*[j]);
visited*[j] = 0;
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(a*[j] == maxm){
Q.push({{i, j}, 0});
visited*[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*, y + dy*) == 1 and visited[x + dx*][y + dy*] == 0){
Q.push({{x + dx*, y + dy*}, d + 1});
visited[x + dx*][y + dy*] = 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)