There are two distinct phases to any problem like this: 1) describe the algorithm you will use to solve the problem, and 2) write an implement in a programming language. It's important to really have a grasp on step 1 before you start on step 2. So how would you describe, in English or in pseudocode, how you would tackle the problem? (Imagine you are solving it yourself using pencil and paper, but further suppose that you are extremely nearsighted so that you can only see one entry of the matrix and its immediate neighbors, at any given time.)
Splitting up the input isn't going to be the hard part. The hard part will be working out the logic to use, which is what Kurt is on about. So you might end up using a StringTokenizer, but you really shouldn't worry about that yet.
I'd suggest starting with the assumption that you've loaded your grid into a two-dimensional array. Don't worry about how you build the array until you know what you're going to do with it. Now, what logical steps are you going to apply to work out your answer?
Writing off the top of my head, my first approach would be something like this:
- Find a '1'
- Now find all the adjacent '1's
- Keep going until I've identified the entire group. I'm going to need some way if remembering which '1's I've already looked at, to make sure I don't count one twice. I'm also going to need a way of remembering the group I've identified, unless I'm only interested in the size (in which case I need to remember that)
- Now find another '1' that wasn't in the first group, and repeat the steps above.
- Was it a bigger group than my previous biggest group? if so, remember it.
- Keep going till there are no more '1's left
Shareef Uddin wrote:
I will try to use stringTokenizer API.
Is that ok?
well...yes...but that is far from complete. Your original question was akin to "how do I build a skyscraper?" and this is like saying "I will try to use a screwdriver". while a screwdriver may be necesary, there is a LOT more going on here.
What I might do is
create a second 2d int array the same size as your input.
create a counter to keep track of which 'group' of 1's you are looking for
initialize each element to '-1'.
find the first element in this array that has a value of -1, which means I haven't looked at it yet.
if the corresponding element in the input array is 0, set it to 0
set the value in the new 2d array to the value of your counter
find all 1's next to this one, and set the corresponding elements to the counter value
find all neighbors of those elements, etc
in this way, you build a second array that keeps track of which 'grouping' a 1-value belongs to. Then, you can go through, count how many elements are in the 1-group, the 2-group, etc.
given your initial input, my new array would look something like
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors