Modification of Flood fill ???

[suchandra]

wasp please share the approach.

should i use floodfil or below algorithm?

https://www.geeksforgeeks.org/find-length-largest-region-boolean-matrix/

[hyfun]

@wasp how??

[akash19jain]

guys could u pls post your code or tell your approach...

[unstoppable13]

@Wasp have you got 100 in expected buildings? because test cases you've shared are of that problem.

[ojEqDjzh]

@Wasp can you please tell us your approach..or post the psuedocode if possible!

[unstoppable13]

find all distinct elements and then use floodfill algorithm for all distinct pairs. after this check for single elements and take maximum of all.In this all you have to do is minimise time of initialising visited array all the time. don't use memset think something different with less time complexity.

[antman]

@unstoppable13 Isn't that O(m*n*m*n)?

[hyfun]

@unstoppable13

"don't use memset think something different with less time complexity."

can u provide any reference site

[tpb]

unstoppable13 wrote:

don't use memset think something different with less time complexity

I assume you mean memcpy.
Just negating the numbers might do, I suppose.

I don't see why the single elements need to be checked. How could one of them possibly be more than the distinct pairs? At most it would be equal.

If a brute force algo can solve this then that's very disappointing. I was hoping for something interesting like DP.

[unstoppable13]

@tpb single elements are required to check because I am checking for distinct elements pair only.....both can't be same that is why it takes less time. And think what to use instead of memset yourself don't ask that to me.

[tpb]

unstoppable13 wrote:

And think what to use instead of memset yourself don't ask that to me.

Hey idiot! I never asked you what to use instead of "memset". I thought you may have been mistaken to even mention memset and that you actually meant to say memcpy. However, I don't care what you meant or said or will ever say in the future, so forget about it. And you obviously don't understand my comment about the single elements.

[closed account 3UohqMoL]

Can anyone tell abt two flowers

[suchandra]

@tpb
lol.. :))

[iGEqDjzh]

@unstoppable Can you share a link for Floodfill algorithm?
I have studied floodfill algorithm but I encountered a problem which is how to determine the index at which we should call the floodfill algorithm. To explain the problem :
Let us consider a pair (1, 2) for this matrix:
4 5
1 3 3 3 1
3 3 2 1 2
5 2 5 1 2
1 3 1 2 1

if I call the floodfill algorithm at (0,0) then it will only index (0,0) whereas if call on (0,4) then the number of flowers return would be (or indices covered) will be total 9.
Am I missing something here ? Could you please clarify this.

[iGEqDjzh]

@tbp I think what you are saying is correct, there is no need to check for the single elements once we have checked for all the distinct pairs. However there is one case where we should check is when all the elements of the matrix are equal but this can be easily handled with an if else statement...

[suchandra]

ohh man, this is worse.

1	0	WA
(0.080000)
1	1	AC
(0.080000)
1	2	WA
(0.080000)
1	3	WA
(0.080000)
1	4	AC
(0.090000)
Subtask Score: 0.00%	Result - WA
2	5	WA
(0.290000)
2	6	AC
(0.260000)
2	7	TLE
(8.010000)
2	8	WA
(0.330000)
2	9	AC
(0.330000)
Subtask Score: 0.00%	Result - WA
3	10	WA
(0.500000)
3	11	AC
(0.420000)
3	12	WA
(0.620000)
3	13	WA
(0.560000)
3	14	AC
(0.600000)
Subtask Score: 0.00%	Result - WA
Total Score = 0.00%

[lastchance]

Rule out the special case of "all-equal" first, then ...

Mark all the connectors between adjacent DISTINCT pairs (e.g. using either one array of structs, or two arrays of bools).

For each available connector do a standard stack-based flood-fill
https://en.wikipedia.org/wiki/Flood_fill
based on the TWO values linked by that connector. Make sure that you remove the available connectors during the flood-fill, or you will end up reproducing this fill many times and getting a TLE.

Update the largest floodfill area as you go along.


Please use this forum responsibly - it is not a social-media platform.

[keve]

#include <stdio.h>
#include<math.h>
int n,m,ct;
int a[100][100];
void check(int i,int j)
{
if(a[i][j]==0)
return;
a[i][j]=5;
ct++;
if(i+1<n&&a[i+1][j]==1 || a[i+1][j]==2){
check(i+1,j);

}
if(i-1>=0&&a[i-1][j]==1 || a[i-1][j]==2){
check(i-1,j);

}
if(j+1<m&&a[i][j+1]==1 || a[i][j+1]==2){
check(i,j+1);

}
if(j-1>=0&&a[i][j-1]==1 || a[i][j-1]==2){
check(i,j-1);

}

}
int main() {
while(scanf("%d%d",&n,&m)!=EOF)
{
int tt;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{tt=scanf("%d",&a[i][j]);}//printf("%d ",a[i][j]);}
//puts("");
}
//continue;
int ans=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(a[i][j]==1 || a[i][j]==2)
{
ct=0;
check(i,j);
if(ct>ans) ans=ct;
}
}
}
printf("%d\n",ans);
}
return 0;
}

// SOME AC AND SOME WA with this solution

[keve]

can anyone tell that
what are changes have to made in the solution of this two flower question to get all AC

uptil now it is giving -
1 0 WA (0.000000)
1 1 AC (0.000000)
1 2 WA (0.000000)
1 3 WA (0.000000)
1 4 AC (0.000000)
Subtask Score: 0.00% Result - WA
2 5 WA
(0.140000)
2 6 AC
(0.140000)
2 7 WA
(0.220000)
2 8 WA
(0.220000)
2 9 AC
(0.110000)
Subtask Score: 0.00% Result - WA
3 10 WA
(0.550000)
3 11 AC
(0.620000)
3 12 WA
(0.520000)
3 13 WA
(0.520000)
3 14 AC
(0.500000)
Subtask Score: 0.00% Result - WA
Total Score = 0.00%

[keve]

can anyone help me with the two flower question.
i m getting the above output from the given above code.

please help me.