Count clouds in a 2d array

Question

I am trying to figure out this problem from CodeFights but I don't have much experience with graph traversal so I'm struggling. One of the hints I read for this particular problem was "graph traversal" so I did a BFS but I'm not sure how to get the number of clouds.

For whatever reason with this problem and many other problems, my mind tends to go blank when it comes time to write code for it. I approached the problem as trying to find the contiguous 1's but to no avail. Can anyone help me please?

https://codefights.com/interview/pDTvSuHBgAB9dz5ik/companies/N3sScnJbzdPDQaHPj

Given a 2D grid skyMap composed of '1's (clouds) and '0's (clear sky), count the number of clouds. A cloud is surrounded by clear sky, and is formed by connecting adjacent clouds horizontally or vertically. You can assume that all four edges of the skyMap are surrounded by clear sky.

Example

skyMap = [['0', '1', '1', '0', '1'],
         ['0', '1', '1', '1', '1'],
         ['0', '0', '0', '0', '1'],
         ['1', '0', '0', '1', '1']]

the output should be countClouds(skyMap) = 2;

skyMap = [['0', '1', '0', '0', '1'],
         ['1', '1', '0', '0', '0'],
         ['0', '0', '1', '0', '1'],
         ['0', '0', '1', '1', '0'],
         ['1', '0', '1', '1', '0']]

the output should be countClouds(skyMap) = 5.

I can see that even *one* unsurrounded cell of `1` as a value is considered as a cloud, Am I wrong ? — Yahya, Jun 13 '17 at 18:47
DFS works just as well. You should keep a Boolean array that stores true if a node has been visited, and false otherwise. Traverse recursively over the 2D array, each time going a level deeper if a node hasn't been visited. If a node has been visited, move onto the next one, otherwise increment a counter and recurse. Stop when you've visited all nodes. — cs95, Jun 13 '17 at 18:47
I would create a method that checks the the neighbors every time you invoke it, and then traverse recursively the array. Please see [this answer](https://stackoverflow.com/questions/44318545/matrix-traversal-by-expanding-outwards-from-a-point/44319101#44319101) which has a start point for your project. — Yahya, Jun 13 '17 at 18:52
The duplicates solve a more complex version of this problem, but the same approaches can be used here. Similar to [Number of Groups/Islands of 1's in a Matrix: Definition clarification](https://stackoverflow.com/questions/33957209/number-of-groups-islands-of-1s-in-a-matrix-definition-clarification) as well. — Bernhard Barker, Jun 13 '17 at 18:58
@Dukeling Thanks! I searched for a handful of things but never found these. — andsec, Jun 13 '17 at 19:03

score 0 · Answer 1 · answered Jun 13 '17 at 18:52

Here's a crude way of solving the problem. You should try to improve upon this though.

public static void removeCloud(int x, int y, int[][] sky) {
    sky[x][y] = 0;
    if(x > 0 && sky[x-1][y] == 1) {
        removeCloud(x-1,y,sky);
    ...
}

public static int countClouds(int[][] sky) {
    int count = 0
    for(int i = 0; i < sky.length; i++) {
        for(int j = 0; j < sky[i].length) {
            if(sky[i][j] == 1) {
                count++;
                removeCloud(i,j,sky);
            }
        }
    }
}

Count clouds in a 2d array

1 Answers1