Exercice 1: Create a program that, using a 2D array that represents an image with pixels that represent islands surrounded by water, will count the number of islands found surrounded by water. '-' represent the island and '#' is the water. All pixels that are adjacent on the vertical or horizontal are considered as the same island. The program must contain a main method that open an input file name islands.txt and outputs islands.solution.txt .

islands.txt:

Line 1 contains an integer n that represents the number of problems included in the file. The rest of the lines contain n input arrays of pixels. Each input begins with a line containing a pair of integers 1 m, n 100. This line is followed by m lines, each containing exactly n pixels.

The output file, named islands.solution.txt, contains n lines, one per problem. Each line includes a single integer, representing the number of unique islands observed in the corresponding input. Part of an island can still be counted as an observation of an island.

Example:

7 83 -#-##-###-#-##########---#-###---#######-#############-#####-#-#-###-#######-####-# ###########-######-######-######--####-########-##########---#-#-####-#####-#-###-# ##-#######-####-######-##-#####-#--#-######--#####-############-#####--####--#####- ##-###########-############-###############-#####################-###-####--#####-- ############-#-#-###-##-########-##############-##############----###-#########-### ############--############--##########--####-########-###########-###############-# -#--#####-######--##-#-#-#-######-#########-#################-#-#####--#-##-#######

will give the solution 62 in the output file.

I am in a data structures class, I'm guessing we need to choose one of the techniques we saw in class. We have seen:

heaps and heapsort, bst and avl trees, red black trees, disjoint sets, greedy algos,elementary graph algos, topological sort and strongly connected components, mst, single source shortest path, bipartite graphs,network flows, dynamic programming, divide and conquer, amortized analysis, randomized algos.