import java.util.*;
...
Scanner sc = new Scanner(inputfile);
It turns out the * wildcard refers to
this class.
Prefer to list {Scanner, LinkedList} classes explicitly,
as an aid to grep and to eyeballs.
Also, since you're getting ready to merge down to main,
it's time to delete the System.in comment.
You chose map dimensions of x, y, which is kind of OK.
Consider renaming to w, h or width, height.
You put the (0, 0) origin at top rather than bottom,
which seems like it's worth a // comment.
Or better, just assign to map[i][y - j].
The call to bfs omits the counter variable which
the loop is very nicely maintaining.
Consider changing the Public API of bfs to accept
a color parameter, which would simply be the counter.
This might simplify debugging and
allow for more informative map analysis displays.
The idea is that, instead of merely saying
"yup, this is land that Hansel & Gretel placed
a breadcrumb on", we can uniquely name each
island with a distinct integer, and use that
at display time.
This can make a big difference when you're considering
maps or algorithms that might use the
4- or
8-
cell neighborhood,
and you're trying to identify where
flood fill
leaked from one region into an unexpected region.
The visited matrix would be promoted from boolean to integer.
main() is clearly doing more than
one thing.
Break out a pair of read_map, color_map helpers.
It is unclear why you include map reading as
part of the elapsed time measurement,
given that the bfs algorithm is the one of interest.
queue.offer(new int[] { i, j });
I don't understand this line; please add a // comment.
The common idiom would be queue.addLast(),
which is obviously being evaluated for side effects
since it is of type void.
Why do we instead call a boolean valued function
and then choose to discard its return value?
Is this some java checked-exception craziness
where there's a burden to coping with potential exceptions?
Apparently the same thing is going on
when we .poll() instead of .removeFirst().
Please declare a MANIFEST_CONSTANT for this
magic character:
'@'.
I see that we define an Island w.r.t. the
4-cell
neighborhood. Please document that.
There's four lines of source to handle each of four directions.
This is tedious.
Minimally you should extract a trivial helper
so we have one-line calls.
Better would be to define a vector of (delta_x, delta_y)
offsets, and iterate through that.
You told me the bfs loop processes in excess
of eleven million cells per second, and that is not enough.
Sounds pretty quick to me, but OK.
There's a lot of allocations going on,
and you didn't provide any GC stats,
so it's hard to know where to drill down.
The (x, y) Point allocations are perhaps
unavoidable? That is, we could have a
pool of Points at the app level and recycle them, but I
don't see any reason why that would be
more efficient than what the JVM is doing.
The LinkedList .offer() allocations, OTOH,
seem ripe for improvement.
When we .poll() we're doing random read against DRAM,
hoping it plays nicely with the several levels of cache.
I note that you have less than 4 billion cells on the map,
so a point's location can fit within 32 data bits.
You're probably messing with 64-bit object pointers.
We have a queue of unknown size,
which could be a valid motivation for LinkedList.
I propose that we instead store the queue in an ArrayList
having a small initial size, and at the app level we
double its size each time it gets full (or factor
of 1.3 instead of 2, whatever). It never shrinks.
We maintain {front, back} integer indexes into this Circular Queue.
Note that sequential raster scans of an ArrayList
perform better on Intel hardware than scans of LinkedList,
since fetch prediction is easy and we're asking
DRAM for adjacent values so the {CAS, RAS} timing
can stream them out at closer to the bus bandwidth.
I imagine that max queue depth mostly scales with
map width, and can be a bit more than map width
while exploring oddly shaped islands.
Here is a much crazier performance idea:
read in the map lazily.
That is, only read a line of input when forced to
by an array de-reference.
Upon noticing that "count of processed cells"
in first raster is equal to map width,
output that raster and delete it, recycle the memory.
The idea is to have a narrow band of the map
in play at any given moment, hopefully just
a fraction of the ten-thousand rasters.
Of course, island shapes can work against this,
especially if they are designed by an adversary.
Here's another idea, which again depends
on the data pattern of typical input maps.
Reduce the resolution.
That is, turn a 6x2 map into a 3x1 map
of cells colored according to the max()
function. So if any cell in a 2x2 grid is land,
the corresponding supergrid shall be land.
Solve this smaller problem with BFS flood fill,
identifying N islands.
Now you have N sub-problems to solve at normal resolution,
each needing just a reduced memory footprint.
If the technique proves helpful on typical inputs,
notice that you are free to reduce resolution more than once.
Perhaps typical islands are uncooperative and
they thwart those attempts to use less RAM.
Deterministically insert lines of water into
your map, both horizontal and vertical.
Again you have some simpler sub-problems to solve.
Having done that, come back to stitch the islands
back together, repairing damage done by your lines.
You will want to switch from boolean to int color
in order to correctly accomplish that.
Come to think of it, there's no particular reason
to introduce such lines.
What I'm trying to do is get to a spot where
we can conveniently use a standard pre-packaged
spanning tree
algorithm to find connected components
of an undirected graph.
Now strictly speaking the map we initially read in is
such a graph, with each
node having at most a degree of 4.
It just wouldn't be attractive to run Prim
over that; flood fill is a better match
for bulk data reduction.
But suppose we run bounded BFS flood fill,
which terminates upon identifying the K-th island cell,
where we have perhaps K = 1000.
We're giving each pseudo-island a distinct integer identifier, and we understand that we'll have to
come back to merge small pseudo-islands into
giant proper islands.
Shooting a spanning tree through those nodes
would be a good way to merge together
each connected component.
What does this data-reduction buy us?
Flexibility on problem size and memory footprint,
even for extremely large input maps.
We could run a JVM with low memory setting,
or run on a tiny Raspberry Pi,
and later come back to finish the job,
stitching fragments into the larger islands
required for the end product.
The code achieves many of its design objectives.
We have explored avenues for improvement.
I would be willing to delegate or accept maintenance
tasks on this code.
