I drive along a road with my car and it begins to rain. The raindrops are falling on my window randomly and now i ask myself, where is the biggest connected wet area?
To make it easier, the window is split in a matrix of 10*10 squares. Your job is to find the biggest connected water-drop-area on the window.
There are two possible inputs, you can use a 2-dimensional Array or a 1-dimensional one. You can choose between any inputs like stdin, etc...
// 2-dimensional: [[0,1,0,0,0,0,1,0,0,0], [0,1,1,0,0,0,0,1,1,0], [0,1,1,0,0,0,0,1,0,0], [0,1,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,1,0], [0,0,0,1,1,0,0,0,1,0], [0,0,0,1,1,0,0,0,1,0], [0,0,0,0,0,1,1,0,1,0], [0,0,0,0,0,1,1,0,1,0], [0,0,0,0,0,0,0,0,0,0]] // 1-dimensional [0,1,0,0,0,0,1,0,0,0, 0,1,1,0,0,0,0,1,1,0, 0,1,1,0,0,0,0,1,0,0, 0,1,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,1,0, 0,0,0,1,1,0,0,0,1,0, 0,0,0,1,1,0,0,0,1,0, 0,0,0,0,0,1,1,0,1,0, 0,0,0,0,0,1,1,0,1,0, 0,0,0,0,0,0,0,0,0,0]
Your code has to put out the size of the biggest connected area and the x- and y-coordinates of the waterdrops which belong to this area in the format
"Size: Z Coordinates: (X1,Y1) (X2,Y2) ..."
Example for the previous input:
Size: 6 Coordinates: (1,0) (1,1) (2,1) (1,2) (2,2) (1,3)
The order of the Coordinates doesn't matter.
- Waterdrops are connected, if they touch each other orthogonally
- Diagonal connections don't count
- There can be many areas and your code has to find the biggest one
- An empty field is represented as "0" and a wet field as "1"
- Post your solution with a short explanation and the output of the previous input
- The shortest code within the next 7 days will win
- If there are two areas with the same size, you can choose one