Cách đếm số đảo trong ma trận cho trước bằng C#

Quét tuyến tính bản đồ lưới 2D, nếu một nút chứa '1', đó là nút gốc kích hoạt Tìm kiếm theo chiều sâu (DFS). Trong DFS, mọi nút đã thăm được đặt thành '0' để đánh dấu đã thăm. Đếm số nút gốc kích hoạt DFS, con số này chính là số đảo vì mỗi DFS bắt đầu từ một nút gốc xác định một đảo.

Ví dụ

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));
        }
    }
}

Kết quả

2

Giải thích: Ma trận 4x5 có 2 đảo (liên thông 4 chiều). Đảo lớn ở góc trên trái, đảo nhỏ đơn lẻ ở góc dưới phải. DFS đệ quy đánh dấu các ô '1' liên thông thành '0' đã thăm.