The basic floodfill algorithm finds the largest connected area having only a single value.
But instead of binary 2D array, input is a matrix of n*m with numbers;
an island is defined by 2 numbers.
4 5
1 1 2 3 1
3 1 2 5 2
5 2 1 5 6
1 3 1 2 1
ans :-
1 1 2 . .
. 1 2 . .
. 2 1 . .
. . 1 2 1
for island defined by 1 and 2.
. . 2 . .
. . 2 5 2
. . . 5 .
. . . 2 .
for island defined by 2 and 5
find max area of island.
The numbers in array are from 1 to 4*1e6;
size of matrix is max. 2*1e3;
The problem says the area should be sideways connected but for the area to be connected it must also be connected downwards to the same values.Am i correct??
If i am then we can store the pair of each value with the numbar that appers max no. of times in a row and at last output that count it will be very simple but i think that the column too has to be connected
can anyone provide me some test cases that i can use for checking my code?
my code giving right answer for all the test cases that i used bt it give wrong amswer on submission
@Wasp
I tried finding all unique pairs that exist in the matrix using a set in a traversal
and the a Floodfill for each of these pairs but it gives TLE on 3 cases
Sub-Task Task # Result
(time)
1 0 AC (0.010000)
1 1 AC (0.000000)
1 2 AC (0.490000)
1 3 AC (0.000000)
1 4 AC (0.000000)
Subtask Score: 20.00% Result - AC
2 5 AC (0.270000)
2 6 AC (0.080000)
2 7 TLE (4.010000)
2 8 AC (3.380000)
2 9 AC (0.200000)
Subtask Score: 0.00% Result - TLE
3 10 AC (1.040000)
3 11 AC (0.310000)
3 12 TLE (4.010000)
3 13 TLE (4.010000)
3 14 AC (0.760000)
Subtask Score: 0.00% Result - TLE
@rish123y Well done can u share your code so that i we can optimise it for other subtasks.
I also got 20 pts but i traversed all the matrix and didnt used flood will i think ur code can be optimised a little bit
Sub-Task Task # Result
(time)
1 0 AC
(0.000000)
1 1 AC
(0.000000)
1 2 AC
(0.610000)
1 3 AC
(0.010000)
1 4 AC
(0.000000)
Subtask Score: 20.00% Result - AC
2 5 AC
(0.700000)
2 6 AC
(0.060000)
2 7 AC
(3.900000)
2 8 AC
(3.480000)
2 9 AC
(0.400000)
Subtask Score: 20.00% Result - AC
3 10 AC
(2.750000)
3 11 AC
(0.270000)
3 12 AC
(3.010000)
3 13 AC
(3.210000)
3 14 AC
(1.600000)
Subtask Score: 60.00% Result - AC
Total Score = 100.00%
Sub-Task Task # Result
(time)
1 1 AC
(0.020000)
1 2 AC
(0.020000)
Subtask Score: 5.00% Result - AC
2 3 AC
(0.010000)
2 4 AC
(0.000000)
Subtask Score: 15.00% Result - AC
3 5 AC
(0.010000)
3 6 AC
(0.020000)
Subtask Score: 20.00% Result - AC
4 7 AC
(0.060000)
4 8 AC
(0.060000)
4 9 AC
(0.050000)
4 10 AC
(0.060000)
4 11 AC
(0.060000)
Subtask Score: 60.00% Result - AC
Total Score = 100.00%