C# getting the biggest area of a matrix which has the same element

Question

In C# I've come to a problem I can't solve myself. I have a 2d matrix which looks like this

1 1 1 0 0 0 0 1 1 1
1 0 1 0 0 0 0 1 1 1
1 0 1 1 1 1 1 0 1 1
1 0 1 1 1 1 1 0 1 1
1 0 1 1 1 1 1 1 1 1
1 1 1 0 0 1 1 1 1 1
1 1 1 0 0 1 1 1 1 1

I want to find out the biggest 4-connected (north, west, south, east) area of 0. For the example above the answer is 8 (the biggest area of all zeroes is on the top of the matrix):

0 0 0 0
0 0 0 0

I have no idea how to cope such a task, so anything could help.

Thanks!

I've tried iterating through the matrix with a for but its not working if the biggest area where 0 are on the same line (or column).

Have look at https://stackoverflow.com/questions/74278474/recursion-stack-overflow-and-i-dont-understand-why/74278557#74278557 the only difference that there `1` instead of `0` — Dmitry Bychenko, Nov 03 '22 at 09:59
Check https://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1s-in-a-binary-matrix/ it will help you. After this you only have to calculate the area of the resulting matrix — AoooR, Nov 03 '22 at 10:01

Dmitry Bychenko · Answer 1 · 2022-11-03T16:20:35.507

You can scan the map and on each 0 perform a search (in the code below it is Breadth First Search):

Code: (Fiddle)

private static int MaxIsland(int[,] ocean) {
  int result = 0;

  if (ocean == null)
    return result;

  var visited = new HashSet<(int y, int x)>();

  for (int y = 0; y < ocean.GetLength(0); ++y)
    for (int x = 0; x < ocean.GetLength(1); ++x) {
      if (ocean[y, x] != 0)
        continue;
      if (!visited.Add((y, x)))
        continue;

      int current = 1;
      var agenda = new Queue<(int y, int x)>();

      agenda.Enqueue((y, x));

      while (agenda.Count > 0) {
        var (r, c) = agenda.Dequeue();
 
        for (int d = 0; d < 4; ++d) {
          int newR = r + (d - 1) % 2;
          int newC = c + (d - 2) % 2;

          if (newC < 0 || newR < 0 || 
              newR >= ocean.GetLength(0) || newC >= ocean.GetLength(1))
            continue;
          if (ocean[newR, newC] != 0)
            continue;
          if (visited.Add((newR, newC))) {
            agenda.Enqueue((newR, newC));
            current += 1;
          }
        }
      }

      result = Math.Max(result, current);
    }

  return result;
}

Time complexity: O(n * m) where n and m are matrix dimensions

Space complexity: O(n * m) in the worst case

C# getting the biggest area of a matrix which has the same element

1 Answers1