1

This is the code for calculating the number of islands in the grid. Given an m x n 2D binary grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

(This is a question from leetcode)

Eg-

Input: grid =

[
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]

Output: 3

Constraints:

 - `m == grid.length`
 - `n == grid[i].length`
 - `1 <= m, n <= 300`
 - `grid[i][j] is '0' or '1'.`

I have solved it using graphs by finding the total number of connected components. I used a map to point the (i,j) pair to its corresponding vertex number, an adjacency list to store all the edges, and a visited array to mark the vertices that have already been visited.

Here is the code: 

void dfs(vector<vector<int>> edges, bool *visited, int start)
{
    visited[start] = true;

    int n = edges[start].size();
    for (int i = 0; i < n; i++)
    {
        if (!visited[edges[start][i]])
            dfs(edges, visited, edges[start][i]);
    }
}

int numIslands(vector<vector<char>> &grid)
{
    int m = grid.size();
    int n = grid[0].size();

    int start = 0;
    unordered_map<string, int> map;

    //storing the ij pair as a string and giving it an integer value to make it a vertex
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (grid[i][j] == '1')
            {
                char first = '0' + i;
                char second = '0' + j;
                string str = "";
                str += first;
                str += second;
                map[str] = start;
                start++;
            }
        }
    }

    vector<vector<int>> edges(start);

    //adjacency list
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (grid[i][j] == '1')
            {
                char first = '0' + i;
                char second = '0' + j;
                string str = "";
                str += first;
                str += second;

                if (i - 1 >= 0 && grid[i - 1][j] == '1')
                {
                    char first = '0' + (i - 1);
                    char second = '0' + j;
                    string str1 = "";
                    str1 += first;
                    str1 += second;
                    edges[map[str]].push_back(map[str1]);
                }
                if (i + 1 < m && grid[i + 1][j] == '1')
                {
                    char first = '0' + (i + 1);
                    char second = '0' + j;
                    string str1 = "";
                    str1 += first;
                    str1 += second;
                    edges[map[str]].push_back(map[str1]);
                }
                if (j - 1 >= 0 && grid[i][j - 1] == '1')
                {
                    char first = '0' + i;
                    char second = '0' + (j - 1);
                    string str1 = "";
                    str1 += first;
                    str1 += second;
                    edges[map[str]].push_back(map[str1]);
                }
                if (j + 1 < n && grid[i][j + 1] == '1')
                {
                    char first = '0' + i;
                    char second = '0' + (j + 1);
                    string str1 = "";
                    str1 += first;
                    str1 += second;
                    edges[map[str]].push_back(map[str1]);
                }
            }
        }
    }

    //counting the number of connected components
    bool *visited = new bool[start];
    for (int i = 0; i < start; i++)
        visited[i] = false;
    int ans = 0;
    for (int i = 0; i < edges.size(); i++)
    {
        if (!visited[i])
        {
            ans++;
            dfs(edges, visited, i);
        }
    }
    return ans;
}

The code works fine for most of the test cases. However, when I entered one row of input with any number of columns greater than 256, it does not give the desired output(ie, 1).

Eg - [['1', '1', '1', '1', '1', ....(287 times) ]] gives 32 as output.

Why is that the case?

Rushikesh Talokar
  • 1,515
  • 4
  • 16
  • 32
Yesha Majmundar
  • 49
  • 1
  • 2
  • 6
  • 2
    *Why is that the case?* -- [What is a debugger, and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems). – PaulMcKenzie Jun 01 '21 at 01:39
  • 2
    its because first & second datatype is char & it can go upto 255 – Rushikesh Talokar Jun 01 '21 at 01:39
  • What would happen if you replaced all instances of the keyword `char` with `int`? – mattlangford Jun 01 '21 at 01:41
  • 1
    `char first = '0' + i;` - There is no need to make this a char, or even have a `first` variable at all. Just `str += std::to_string(i);`. Same thing on the other lines of code that look like this. – PaulMcKenzie Jun 01 '21 at 01:53
  • 1
    A `char` is not required to be able to represent a value greater than 255. And, in most implementations, it does not. It is implementation-defined whether a `char` is `signed` or `unsigned` type. If it is a `signed` type, then it is only guaranteed (by the standard) able to represent values from `-127` to `127` and, if it is an `unsigned` type, it is only guaranteed able to represent values from `0` to `255`. If you need a larger range of values, use a type that can represent (at least) the range you need. – Peter Jun 01 '21 at 04:17

1 Answers1

1

Here is my approach:

  • Reformat input file. Remove unneccesary characters ( [ ] " , ) and add file and line format identification. This is a trivial task for a decent test editor - I use textpad
format islands
o 1 1 0 0 0
o 1 1 0 0 0
o 0 0 1 0 0
o 0 0 0 1 1

Some code to read the input file

   std::vector<std::vector<char>> grid;
    int RowCount = 0;
    int ColCount = -1;
    std::string line;
    while (std::getline(myFile, line))
    {
        std::cout << line << "\n";
        auto token = ParseSpaceDelimited(line);
        if (!token.size())
            continue;
        switch (token[0][0])
        {
        case 'o':
        {
            if (ColCount == -1)
                ColCount = token.size() - 1;
            else if (token.size() - 1 != ColCount)
                throw std::runtime_error("Bad column count");
            std::vector<char> row;
            for (int k = 1; k < token.size(); k++)
                row.push_back(token[k][0]);
            grid.push_back(row);
        }
        break;
        }
    }
    RowCount = grid.size();

Some code to add graph nodes wherever land occurs. This uses the the PathFinder C++ wrapper for the boost graph library

for (int row = 0; row < RowCount; row++)
{
    for (int col = 0; col < ColCount; col++)
    {
        if (grid[row][col] == '1')
            myFinder.addNode(
                orthogonalGridNodeName(row, col));
    }
}

Some code to link the land nodes together orthogonally

for (int row = 0; row < RowCount; row++)
{
    for (int col = 0; col < ColCount; col++)
    {
        int n = row * ColCount + col;

        if (col < ColCount - 1)
        {
            if (grid[row][col] == '1' && grid[row][col + 1] == '1')
            {
                myFinder.addLink(
                    orthogonalGridNodeName(row, col ),
                    orthogonalGridNodeName(row, col + 1 ),
                    1);
            }
        }
        if (row < RowCount - 1)
        {
            if (grid[row][col] == '1' && grid[row + 1][col] == '1')
            {
                myFinder.addLink(
                    orthogonalGridNodeName(row, col ),
                    orthogonalGridNodeName(row+1, col ),
                    1);
            }
        }
    }
}

Finally, as a reward for all this mucking around, two lines of code suffice to calculate the number of islands

int cPathFinder::islandCount()
{
    std::vector<int> component(boost::num_vertices(myGraph));
    return boost::connected_components(myGraph, &component[0]);
}

which outputs:

enter image description here

Complete code for this here

By the way, 280 or so 1's all in a line gives:

There are 1 islands

enter image description here

ravenspoint
  • 19,093
  • 6
  • 57
  • 103