วิธีพิมพ์จำนวนเกาะในแมทริกซ์ที่กำหนดด้วย C#

สแกนแบบเส้นตรงผ่านแผนที่กริด 2 มิติ หากโหนดมีค่า '1' แล้วมันคือโหนดรากที่ทริกเกอร์ Depth First Search ระหว่าง DFS ทุกโหนดที่เยี่ยมชมควรตั้งค่าเป็น '0' เพื่อทำเครื่องหมายว่าเยี่ยมชมแล้ว นับจำนวนโหนดรากที่ทริกเกอร์ DFS จำนวนนี้จะเป็นจำนวนเกาะ เนื่องจากแต่ละ DFS เริ่มจากโหนดรากบางตัวจะระบุเกาะหนึ่ง

ตัวอย่าง

using System;

namespace ConsoleApplication
{
    public class Matrix
    {
        public int PrintNumberOfIslands(char[,] grid)
        {
            bool[,] visited = new bool[grid.GetLength(0), grid.GetLength(1)];
            int res = 0;
            for (int i = 0; i < grid.GetLength(0); i++)
            {
                for (int j = 0; j < grid.GetLength(1); j++)
                {
                    if (grid[i, j] == '1' && !visited[i, j])
                    {
                        DFS(grid, visited, i, j);
                        res++;
                    }
                }
            }
            return res;
        }

        public void DFS(char[,] grid, bool[,] visited, int i, int j)
        {
            if (i < 0 || i >= grid.GetLength(0)) return;
            if (j < 0 || j >= grid.GetLength(1)) return;
            if (grid[i, j] != '1' || visited[i, j]) return;
            visited[i, j] = true;
            DFS(grid, visited, i + 1, j);
            DFS(grid, visited, i - 1, j);
            DFS(grid, visited, i, j + 1);
            DFS(grid, visited, i, j - 1);
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Matrix m = new Matrix();
            char[,] mm = { { '1', '1', '1', '1', '0' }, { '1', '1', '0', '1', '0' }, { '1', '1', '0', '0', '0' }, { '0', '0', '0', '0', '1' } };
            Console.WriteLine(m.PrintNumberOfIslands(mm));
        }
    }
}

ผลลัพธ์

2