program SNSOCIAL;
var T1, n, t, m, i, j, k, mx, demluot,u,v: longint;
a: array[0…501, 0…501] of longint;
b: array[0…501, 0…501] of integer;
begin
readln(T1);
for i:= 1 to T1 do
begin
readln(n, m);
mx := 0;
for j:= 1 to n do
for k:= 1 to m do
begin
read(a[j, k]);
b[j,k] := m+n;
if mx<a[j, k] then mx := a[j,k];
end;
for j:= 1 to n do
for k:= 1 to m do
if(a[j, k] = mx) then
begin
b[j, k] := 0;
t:=1;
while (j-t>=1) or (j+t<=n) or (k-t>=1) or (k+t<=n) do
begin
for u:= j-t to j + t do
if(u>=1) and (u<=n)then
begin
if (k-t>=1) and (t<b[u, k-t]) then b[u, k-t] := t;
if (k+t<=n) and (t<b[u, k+t]) then b[u, k+t] := t;
end;
for v:= k-t to k + t do
if(v>=1) and (v<=n) then
begin
if (j-t>=1) and (t<b[j-t, v]) then b[j-t, v] := t;
if (j+t<=n) and (t<b[j+t, v]) then b[j+t, v] := t;
end;
t:= t+1;
end;
end;
demluot := 0;
for j:= 1 to n do
for k:= 1 to m do
if demluot < b[j,k] then demluot := b[j,k];
write(demluot);
if i<>T1 then writeln;
end;
struct Point{
int x;
int y;
};
void changeAll(vector<Point>& tempset,int a[][500],Point p,int n,int m){
int row = p.y;
int col = p.x;
int element = a[row][col];
Point t;
if((row-1)>=0 && (col-1) >=0 && a[row-1][col-1]!=-1 && a[row-1][col-1]!=element ) // upper left corner
{
a[row-1][col-1]=element ;
t.x = col-1;
t.y = row-1;
tempset.push_back(t);
}
if(col-1 >=0 && a[row][col-1]!=-1 && a[row][col-1]!=element) // same row col -1
{
a[row][col-1]=element ;
t.x = col-1;
t.y = row;
tempset.push_back(t);
}
if((row+1) < n && (col -1) >=0&&a[row+1][col-1]!=-1 && a[row+1][col-1]!=element )
{
a[row+1][col-1]=element ;
t.x = col-1;
t.y = row+1;
tempset.push_back(t);
}
if((row+1) < n &&a[row+1][col]!=-1 && a[row+1][col]!=element )
{
a[row+1][col]=element ;
t.x = col;
t.y = row+1;
tempset.push_back(t);
}
if((row+1) < n && (col +1) < m &&a[row+1][col+1]!=-1 && a[row+1][col+1]!=element )
{
a[row+1][col+1]=element ;
t.x = col+1;
t.y = row+1;
tempset.push_back(t);
}
if(col+1 < m &&a[row][col+1]!=-1 &&a[row][col+1] != element )
{
a[row][col+1] = element ;
t.x = col+1;
t.y = row;
tempset.push_back(t);
}
if((row-1) >=0 && (col+1) < m&&a[row-1][col+1]!=-1 && a[row-1][col+1]!= element)
{a[row-1][col+1] = element;
t.x = col+1;
t.y = row-1;
tempset.push_back(t);
}
if((row-1) >=0 && a[row-1][col]!=-1 && a[row-1][col] != element)
{
a[row-1][col] = element;
t.x = col;
t.y = row-1;
tempset.push_back(t);
}
return ;}
long int recur(vector<Point> tempset,int a[][500],long int c,int n,int m){
vector<Point>::iterator it;
vector<Point> tempSet;
for(it=tempset.begin();it!=tempset.end();it++)
{Point temp = *it ;
changeAll(tempSet,a,temp,n,m);
a[temp.y][temp.x]= -1;}
if(!tempSet.empty())
{c++;
return recur(tempSet,a,c,n,m);}
else
{return c;}
}
int main(){
----input section-----
vector<Point> myset;
find max in 2D array
Point p;
for(n)for(m)
{ if(a[i][j]==MAX)
{p.x = j;
p.y= i;
myset.push_back(p);
}}}
recur(myset,a,0,n,m);
print it
--end---
I used a storage for all position of MAX in 2D array…i.e vector where location of MAXElement is stored Now iterate over its children i.e connected Points and make this Point as visited(i used -1 for that)…update this children set every time u cover all parent push tham all in vector in next iteration cover these id final set of children is empty stop recursion…Good Day…Banaji
If anybody is interested in an overkill approach, I did it using binary search to set the time taken to make all numbers maximum + RMQ on 2d matrix to check for the maximum condition. You might want to have a look at this problem from JUNE16 and idea of 2d RMQ. Some optimizations will be required to pass time limit. Refer to solutions of JUNE16 CHSQARR problem or my solution.
A good way to see this problem was to implement flood-fill from all the maximum points. I used the method of storing “openSet” and “closedSet” (as lists) as we do in the A* Path finding algorithm.
Initially, the openSet (the matrix positions which needs to be visited next is empty).
The closedSet contains the positions of all the maximum points.
We traverse through the closedSet and push all the non-maximum neighboring points onto the openSet (just like how we do in A* algorithm). For efficiency, we remove the points from the closedSet. (I didn’t have to maintain a closedSet since I used an auxiliary array to store all the ‘visited’ points.
Think of it as coloring the graph (flood-fill). Consider a full white colored graph. First we have some points (maximum valued). We mark these points with red color. Then we mark their non-red neighbors with grey. We get the next layer of points to be colored red. For efficiency, we mark all the currently red points with black (these are the internal points). Now, we mark the grey points with red. Now we repeat. The number of (grey) layers formed will be the answer.
![image][1]
I advise you to check out some videos on A* algorithm and know more about closedSet and openSet.
Here’s my solution:
[2]
De-comment the code to see how the flood-fill is working.
[1]: http://i.imgur.com/HkQYvRO.jpg
[2]: https://www.codechef.com/viewsolution/13948667
i did BFS where all the elements with the maximum value are in the queue initially, that way when any node is popped off that is the minimum distance from any maximum node.
Hello, first time i ask for advice, sorry to bother but this is driving me mad
What i did:
loop on input, find min and max value, and storing their coordinates
then i test if min=max and retrun 0 if so (ie handle first test case)
then for each min coord, i calculate distance between this min and each max
then i keep the minimum of the distance found between this min and every max
then i do the same for every minimum
then i keep the maximum of the minimum found
I use distance between two coordinates = max (delta_x, delta_y)
because wealth propagates diagonally too
propagates with a cost of 1 hour each time
Here are some examples why i chose to do this instead of propagating
dx=4 dx=4 dx=4 dx=4 dx=4 dx=3 dx=2 dx=1 dx=0
dy=0 dy=1 dy=2 dy=3 dy=4 dy=4 dy=4 dy=4 dy=4
d=4 d=4 d=4 d=4 d=4 d=4 d=4 d=4 d=4
AxxxB Axxx Axx Ax A A A A A
B x x x x x x x
B x x x x x x
B x x x x x
B B B B B
So, my submission follows the provided explanation, except for the distance calculation explained above.
My problème is i get “Wrong Answer” and i can’t think of any flaw in what i’ve done !
Could anyone help me in figuring out why my solution failed to accept? I used similar approach as discussed in editorial.
Link to submitted code is CodeChef: Practical coding for everyone . Ps:- Pls provide test case.it will be more helpful.
I tried this question using 2 priority queues.First priority is sorted on the basis of value and second on the basis of time to make that cell max.I am getting WA, can anybody tell me where I went wrong.
