Is there a recursion limit? I get an error like the following only for test case #9:
at Answer.py. not in a function on line 19
at Answer.py. in expand on line 19
...
at Answer.py. in expand on line 19
at Answer.py. in <module> on line 37
(expand is the name of my recursive function)
In Python, yes, it’s internal.
There may be something no one has noticed before. The first four cases are symmetric in the sense that if someone accidentally switches the indices of the double indexed array (definitely not me, for the fifth time 
), but has an otherwise working algorithm, will perfectly pass. I spent about the same time trying to figure out why my program doesn’t work as the time I spent writing it. Good advice: map[i,j] != map[j,i] in general. 
Hi, just got 100% in C++ with plain BFS without any optimizations.
Feel like I have cheated
Look at the other solutions, you are not the only one who “cheated” this way
This puzzle IMHO is too easy for 250xp. Simple BFS gets it done, whereas even skynet 1 required a more careful algo for 150xp
If that’s true, then my code should do very well on it, because it uses an RLE representation of the landscape. Big areas of water are ideal for it, and it runs very fast on the big test cases in the IDE. The slowest one is “100 tests on a 1000x1000 map” at 177ms, due simply to the large number of points tested; “large map, large lake” completes in only 6ms.
Yet “No Land” in the validation suite fails for my Lua solution, and I have no idea why.
I just wrote another solution in C++, and that passes all the tests. (It uses a different algorithm based on sets instead of flood-filling.) I’m left wondering if there’s something funny about that particular test case that mis-parses in Lua.
Can someone please check this code. I implemented the floodfill using the Queues. It shows TLE in the last testcase
import java.util.*;
import java.io.*;
import java.math.*;
/**
* Auto-generated code below aims at helping you parse
* the standard input according to the problem statement.
**/
class Solution {
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
int L = in.nextInt();
int H = in.nextInt();
char[][] q = new char[H][L];
int ctr;
ArrayDeque<Integer[]> aq = new ArrayDeque<Integer[]>();
ArrayList<Integer[]> checked = new ArrayList<Integer[]>();
if (in.hasNextLine()) {
in.nextLine();
}
for (int i = 0; i < H; i++) {
q[i] = in.nextLine().toCharArray();
}
int N = in.nextInt();
int[][] cood = new int[N][2];
for (int i = 0; i < N; i++) {
cood[i][1] = in.nextInt();
cood[i][0] = in.nextInt();
}
int[] co = new int[]{-1,0,1};
//System.err.println(N);
for (int k = 0; k < N; k++) {
aq.clear();
Integer[] SI = new Integer[]{cood[k][0],cood[k][1]};
checked.clear();
ctr = 0;
//System.err.println(q[SI[0]][SI[1]]);
if(q[SI[0]][SI[1]]=='O'){ctr++;checked.add(SI);
aq.push(SI);
do
{
SI = aq.pollLast();
for(int i = 0;i<3;i++)
for(int j = 0;j<3;j++)
{
Integer[] tmp = null;
if(Math.abs(co[i])!=Math.abs(co[j]))
{
tmp = new Integer[]{SI[0]+co[i],SI[1]+co[j]};
try
{
if(q[tmp[0]][tmp[1]]=='O' && notIn(checked,tmp))
{
//System.err.println("Trying : "+(SI[0]+co[i])+","+(SI[1]+co[j]));
aq.push(tmp);
checked.add(tmp);
ctr++;
}
}
catch(Exception e)
{}
}
}
}
while(aq.peekLast()!=null);
}
System.out.println(ctr);
}
}
public static boolean notIn(ArrayList<Integer[]> a, Integer[] q)
{
for(Integer[] i : a)
{
if(Arrays.equals(i,q))
return false;
}
return true;
}
}Looks like your code does not store the lake size. That might be what you are missing. So if a lake is composed of 3 squares (0, 0), (0, 1), (1,0) and you are asked to check the size of lake starting at (0, 0) and (0, 1) … are you going to run your flood-fill algorithm twice?
Hi all.
I didn’t have to do anything special for very large lakes. My approach was able to calculate them all.
I also didn’t calculate anything that wasn’t requested.
I have an array of request numbers initialized to 0 (in C), and an array of integers for map cells, but I store the area in the request array and I store the request number in the map array.
If a cell has water, its map cell is set to -1.
As soon as a cell is requested, if its value is still -1, it is set to the request number. Its neighbors are all checked (via queue / circular buffer), and any that are -1 are added to the queue and set to the request number, and the area is incremented by 1 (being stored in the request array at [reqnumber].
So all cells connected to any cell that has previously been searched will send you to the same value.
Worked on all tests and submission without the need to check for >97% water or such tricks.
Have fun!
Passing the last test on this one was not easy for me. I was using a recursive function going from the target coordinates and propagating to the neighboors until there is no water with a system of cache to avoid doing the recalculations for area I explored already, but it was way to heavy.
I had to start again from the beginning and I changed completly my approach, making a first scan of the full map to generate all the cluster via two dictionnaries: one that memorise the label attributed to a coordinate (x,y), and one that cache the list of all coordinates linked to a label.
This method was way more efficient than my original approach.
TBH I’m not sure if the tag “Recursion” is appropriate for this puzzle. It’s perfectly solvable without and rarely (only on specific languages/with specific optimizations) solvable with recursion.
Also, I agree with Surface puzzle discussion - #55 by CyberLemonade - this puzzle looks a bit too easy for 250xp. Not that I’m complaining… 
Has anyone solved this puzzle using Python ?
I coded BFS (using list and then using dictionary) but i can not pass the final test due to time limit…
And i dont see how to optimize my code…
I’ve solved it using Python and lists and a dictionary too.
Does your code store the area for ALL the points of a particular lake once its area is calculated?
Yes, I did.
I used two structures to store the data.
Yes, entire lake is stored into a list.
if the tested case is ‘O’, I explore the lake using BFS returning a list, and then i simmply do a len(list) to get the surface
What I did was actually associate each point with its area in a dictionary. A list of points may not be as efficient.
I think I understand how you did.
Nevertheless, i can not see how it would work : the final test is just one biiiiig lake and my BFS algo seems too slow to calculate the lake list and then the surface.
Or maybe the way i calculate surface is not good…
Ah, I see what you mean. I also used a set to store the visited points during the search process.
I tried another approach, I used the Union Find algorithm to group the lakes and then I used a dictionary to store the number of lake cells for each parent.