Homework 5: Basic Graphs

Preface

This problem comes directly from a CS 412 student's coding interview with Amazon. The student was given one hour to solve three different problems and this was one of the problems. The easiest way to solve this problem quickly with a minimal amount of code is recursively, which is probably the right way to knock something like this out under coding interview pressure. This is also a very slight twist on a very standard coding interview question.

You only need to code up one implementation and turn it in and I don't care if it's the iterative or the recursive solution; however, I suggest you take the following approach to this problem:

Set aside one hour to approach this problem fresh and attempt to knock out a complete solution to the problem on your first try in under an hour. You haven't been practicing this sort of thing (that is, trying to code under a strict time limit), so its likely that you won't succeed within the hour time limit. The purpose of this exercise is for you go gauge where you are at.
Take your time in coding a solution. I suggest you code both a recursive solution and an iterative solution. These are the sorts of things you should be working to get comfortable with coding as second nature. Obviously, the first time you code it, it will not be second nature yet. You have to do it a lot before it becomes second nature. Practice, as always, makes perfect here. As I always tell students: learning to code is much more like learning a musical instrument than learning a body of facts. You only get better at what you practice. Class time / instruction only exists to point you towards what you need to do, but you have to go and do it.
Once you've coded solutions to the problem, on a different day, set aside another hour for yourself and try to code a solution as quickly as possible without referring to your previous solutions. You've now done the hard work in step 2 of actually solving, coding, and debugging your first solution.

It's time to reinforce those neural pathways in your mind and make this sort of problem a part of your repertoire--every professional cellist in the world can play the prelude to Bach's cello suite in G without preparation (if you don't know the piece, switch to Spotify, load up one of Yo-Yo Ma's recordings of it, then come back here), every computer scientist should be able to bang out a recursive solution to this problem without even thinking about it. But that only comes with practice. I've coded variations of this probably hundreds of times at this point, if not thousands, which is why I can live code it in class with you without having to debug. Y'all are at the point where you have all the knowledge you need and solidifying it practice is the final piece.

So, with Yo-Yo Ma playing Bach's Prelude to the Cello Suite in G in the background try to rewrite your solution from scratch as quickly as possible.

Problem

You have been hired by an elite treasure hunting team to help them find a treasure that was hidden on a large island in the South Pacific. The team has obtained LIDAR scans of a large square patch of ocean and has preprocessed the scans into an n x n array where each array slot is either a 0 or a 1. A 0 denotes ocean while a 1 denotes land. Each array slot corresponds to 1 acre of scan and adjacent slots in the array (in the vertical or horizontal directions, but not diagonal) that both contain a 1 are considered part of the same land mass / island. Your task is to find the size of the largest island in acres.

Input

The input is given by a line containing a single number n followed by n lines, each of which has n values of either 0 or 1 separated by spaces representing the scan of the region.

Output

The output is a single number which is the size of the largest island in the map in acres.

Sample Input

Sample Output

6
0 1 0 0 0 0
0 1 1 0 0 0
0 0 0 1 1 1
0 0 1 1 1 0
0 0 1 1 0 0
1 0 0 0 0 0

8
0 1 0 0 0 0 1 1
0 1 1 0 0 1 1 0
0 0 0 1 1 1 1 1
0 0 1 1 1 0 1 1
0 0 1 1 0 1 1 0
1 0 0 0 0 0 1 1
0 0 0 0 0 1 1 0
0 0 0 0 0 0 1 1

Turning it in

Name your program cs412_islands_a.py and turn it in on Gradescope.