// @nuget: System.ValueTuple

// @nuget: Newtonsoft.Json

using System;

using System.Collections.Generic;

​

/*

标题：LeetCode（力扣）有那些让你直呼内行的算法题解?

题目：给你一个大小为 m x n 的二进制矩阵 grid，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。

一次移动是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。

返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。

输入：grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]

输出：0

解释：所有 1 都在边界上或可以到达边界。

​

作者：力扣（LeetCode）

链接：https://www.zhihu.com/question/496760758/answer/2585168386

来源：知乎

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

*/

​

public class Solution {

    // public static int[][] dirs = {new int[]{-1, 0}, new int[]{1, 0}, new int[]{0, -1}, new int[]{0, 1}};

​

    public static int[][] dirs = {new int[]{0,1,1,0},

                                  new int[]{0,0,1,0},

                                  new int[]{0,0,1,0},

                                  new int[]{0,0,0,0}};

    public static void Main()

    {

​

        Console.WriteLine(NumEnclaves(dirs));

    }

​

    public static int NumEnclaves(int[][] grid) {

        int m = grid.Length, n = grid[0].Length;

        bool[][] visited = new bool[m][];

        for (int i = 0; i < m; i++) {

            visited[i] = new bool[n];

        }

        Queue<Tuple<int, int>> queue = new Queue<Tuple<int, int>>();

        for (int i = 0; i < m; i++) {

            if (grid[i][0] == 1) {

                visited[i][0] = true;

                queue.Enqueue(new Tuple<int, int>(i, 0));

            }

            if (grid[i][n - 1] == 1) {

                visited[i][n - 1] = true;

                queue.Enqueue(new Tuple<int, int>(i, n - 1));

            }

        }

        for (int j = 1; j < n - 1; j++) {

            if (grid[0][j] == 1) {

                visited[0][j] = true;

                queue.Enqueue(new Tuple<int, int>(0, j));

            }

            if (grid[m - 1][j] == 1) {

                visited[m - 1][j] = true;

                queue.Enqueue(new Tuple<int, int>(m - 1, j));

            }

        }

        while (queue.Count > 0) {

            Tuple<int, int> cell = queue.Dequeue();

            int currRow = cell.Item1, currCol = cell.Item2;

            foreach (int[] dir in dirs) {

                int nextRow = currRow + dir[0], nextCol = currCol + dir[1];

                if (nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n && grid[nextRow][nextCol] == 1 && !visited[nextRow][nextCol]) {

                    visited[nextRow][nextCol] = true;

                    queue.Enqueue(new Tuple<int, int>(nextRow, nextCol));

                }

            }

        }

        int enclaves = 0;

        for (int i = 1; i < m - 1; i++) {

            for (int j = 1; j < n - 1; j++) {

                if (grid[i][j] == 1 && !visited[i][j]) {

                    enclaves++;

                }

            }

        }

        return enclaves;

    }

}