PROBLEM LINK:
Author: Pritish Priyatosh Nayak
Tester: Sibasish Ghosh
Editorialist: Pritish Priyatosh Nayak
DIFFICULTY:
Easy
PREREQUISITES:
Graph Theory
PROBLEM:
Given C coordinate of type-1 and D coordinates of type-2.
Let distC denote the manhattan distance from closest type-1 point and
Let distD denote the manhattan distance from closest type-2 point.
Find all the locations in the matrix such that distD less than or equal to distC.
QUICK EXPLANATION:
Use Multisource BFS( or Dikstra’s) to determine all the distances and then print the answer.
EXPLANATION:
It’s a slightly modified standard multisource BFS problem.
The graph vertices being coordinates in the matrix makes the implementation a bit longer.
Otherwise it’s a pretty straight forward problem.
So the approach is to represent the vertices as pairs and use the standard multisource BFS algorithm.
Do it two times for each type of virus and then for each vertex you can get the closest distances from each type of virus.
Whichever virus reaches a vertex first determines whether it will be infected or not.
The total number of vertices and total number of edges to be processed is in the order N \mul M.
So total time complexity of the entire process is O(NMlog(NM)).
SOLUTIONS:
Setter's/Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
typedef struct Node
{
int dist,x,y;
bool operator<(const Node& other) const{
if(this->dist != other.dist)
return this->dist < other.dist;
else if(this->x!=other.x)
return this->x < other.x;
else return this->y<other.y;
}
}node;
int main()
{
int t;
cin>>t;
while(t--)
{
int n,m;
cin>>n>>m;
int dist[2][n][m];
set<node> s[2];
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j){
dist[0][i][j]=inf,dist[1][i][j]=inf;
s[0].insert({inf,i,j});s[1].insert({inf,i,j});
}
for(int idx=0;idx<2;idx++){
int cnt,r,c;
cin>>cnt;
for (int i = 0; i < cnt; ++i){
cin>>r>>c;
r--,c--;
s[idx].erase({dist[idx][r][c],r,c});
dist[idx][r][c]=0;
s[idx].insert({dist[idx][r][c],r,c});
}
}
for(int idx=0;idx<2;idx++)
while(!s[idx].empty())
{
node v=*s[idx].begin();
s[idx].erase(v);
int x=v.x,y=v.y,d=v.dist;
if(x-1>=0)
{
if(dist[idx][x-1][y]>d+1)
{
s[idx].erase({dist[idx][x-1][y],x-1,y});
dist[idx][x-1][y]=d+1;
s[idx].insert({dist[idx][x-1][y],x-1,y});
}
}
if(x+1<n)
{
if(dist[idx][x+1][y]>d+1)
{
s[idx].erase({dist[idx][x+1][y],x+1,y});
dist[idx][x+1][y]=d+1;
s[idx].insert({dist[idx][x+1][y],x+1,y});
}
}
if(y-1>=0)
{
if(dist[idx][x][y-1]>d+1)
{
s[idx].erase({dist[idx][x][y-1],x,y-1});
dist[idx][x][y-1]=d+1;
s[idx].insert({dist[idx][x][y-1],x,y-1});
}
}
if(y+1<m)
{
if(dist[idx][x][y+1]>d+1)
{
s[idx].erase({dist[idx][x][y+1],x,y+1});
dist[idx][x][y+1]=d+1;
s[idx].insert({dist[idx][x][y+1],x,y+1});
}
}
}
int ans=0;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
if(dist[0][i][j]<dist[1][i][j])
ans++;
cout<<ans<<'\n';
}
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
#define mod 1000000007
#define F first
#define S second
#define pb push_back
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
typedef long long int ll;
ll n,m,c,d;
ll dist[2][1001][1001];
multiset<pair<ll,pair<ll,ll> > > ms;
bool check(ll x,ll y)
{
if(x < 1 || x > n || y < 1 || y > m)
return false;
return true;
}
void dijkstra(ll idx)
{
while(!ms.empty())
{
ll d=(*ms.begin()).F;
ll x=(*ms.begin()).S.F;
ll y=(*ms.begin()).S.S;
ms.erase(ms.begin());
if(check(x+1,y))
{
if(dist[idx][x+1][y] > d+1)
{
dist[idx][x+1][y]=d+1;
ms.insert({d+1,{x+1,y}});
}
}
if(check(x-1,y))
{
if(dist[idx][x-1][y] > d+1)
{
dist[idx][x-1][y]=d+1;
ms.insert({d+1,{x-1,y}});
}
}
if(check(x,y+1))
{
if(dist[idx][x][y+1] > d+1)
{
dist[idx][x][y+1]=d+1;
ms.insert({d+1,{x,y+1}});
}
}
if(check(x,y-1))
{
if(dist[idx][x][y-1] > d+1)
{
dist[idx][x][y-1]=d+1;
ms.insert({d+1,{x,y-1}});
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t=1,cnt=0;
cin>>t;
while(t--)
{
ll i,j,x,y,cnt=0;
cin>>n>>m;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
dist[0][i][j]=dist[1][i][j]=1e9;
}
ms.clear();
cin>>c;
for(i=1;i<=c;i++)
{
cin>>x>>y;
ms.insert({0,{x,y}});
dist[0][x][y]=0;
}
dijkstra(0);
ms.clear();
cin>>d;
for(i=1;i<=d;i++)
{
cin>>x>>y;
ms.insert({0,{x,y}});
dist[1][x][y]=0;
}
dijkstra(1);
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(dist[0][i][j] < dist[1][i][j])
cnt++;
}
}
cout<<cnt<<"\n";
}
return 0;
}