-1

I have a Matrix[x][y] of ints that are either 1 or 0 in C#. I need to count how many 0 are in an island, and I was thinking of using a flood fill algorithm but I don't know how to write it. Any ideas?

this is what I did

void FloodFill(int r, int c)
{
    player = FindObjectOfType<Player>();

    r = Mathf.RoundToInt(player.coords.x);
    c = Mathf.RoundToInt(player.coords.y);

    if (matrix[r][c] == 1)
    {
        count++; 
        FloodFill(r + 1 , c);
        FloodFill(r , c + 1);
        FloodFill(r - 1 , c);
        FloodFill(r , c - 1);
    }
}

I don't think is right though.

user10625300
  • 1
  • 2
  • 1
    wikipedia is a great resource. [example](https://stackoverflow.com/questions/45290317/how-can-i-fill-part-of-image-with-color/45299760#45299760) – TaW Nov 08 '18 at 18:27

2 Answers2

1

I will give you the algorithm and leave the coding as exercise.

First create another boolean matrix called visited[x][y]

Loop thru the original matrix row by row and whenever you see a 1, you would first check if it has already been visited using the matrix we created above.

If (a, b) is not visited then you do DFS or BFS starting from (a, b) on all neighbor points that are 1. While you are doing this also mark the visited[a][b] = true.

When you are done with the DFS/BFS for (a, b), increment island count by one and move to (a + 1, b).

You will then have the total count after you have visited (x, y)

Total run time: O(xy)

Steve
  • 11,696
  • 7
  • 43
  • 81
  • Thanks for the answer, but I don't need to run thru the entire matrix, I need the algorithm to start inside an island (the start position is taken from another method) and I need to count how many 0s are in that island the 1s being the borders. I'm using this to check the win condition for a game but I don't know how flood fill works. – user10625300 Nov 08 '18 at 18:36
  • @user10625300 if island inside island is not allowed then you can simply DFS/BFS over all the 0s . simple – Steve Nov 08 '18 at 18:44
  • I'm sorry Steve, but I'm new to programming and I'm trying to understand but I can't. I don't know how to write that. – user10625300 Nov 08 '18 at 19:08
  • @user10625300 https://en.wikipedia.org/wiki/Depth-first_search. I would suggest you try this out on a simple setup first. After you are comfortable with DFS you can then try to apply this on your problem – Steve Nov 08 '18 at 19:44
  • I wrote this code, I posted in the answer below because it was too long – user10625300 Nov 08 '18 at 23:15
  • @user10625300 as I mentioned before. Try to do DFS on something simple first. Do not apply it on your problem until you understand the whole thing . – Steve Nov 09 '18 at 20:39
0

I wrote this, how far off am I ?

void FloodFill()
{
    player = FindObjectOfType<Player>();

    r = Mathf.RoundToInt(player.coords.x);
    c = Mathf.RoundToInt(player.coords.y);

    Stack cells = new Stack();
    Stack visited = new Stack();

    cells.Push(matrix[r][c]);
    while (cells.Count > 0)
    {
        matrix[r][c] = cells.Pop();  //error cannot convert "object" to "int"

        if (matrix[r][c] == 0)
        {
            visited.Push(matrix[r][c]);
            cells.Push(matrix[r + 1][c]);
            cells.Push(matrix[r][c + 1]);
            cells.Push(matrix[r - 1][c]);
            cells.Push(matrix[r][c - 1]);
        }
    }
    visited.Count();   //error "Stack.Count" cannot be used as a method
    return;
}

I know that I'm missing something to check if the cell have been visited, and there are errors that i don't know how to addres

user10625300
  • 1
  • 2