如何使用C#实现战舰游戏10×10棋盘内的舰船总数计算功能

需求说明 #

统计10×10棋盘中的舰船总数，规则如下：

• 棋盘数值1代表舰船组成部分，0代表水域
• 上下左右相邻的1属于同一艘舰船

实现思路 #

采用沉没法统计连通块数量：
遍历棋盘每个单元格，每发现一个未被统计的舰船（值为1），就将计数+1，随后将当前舰船所有连通的1全部改为0，避免重复统计。

完整实现代码 #

namespace Ships
{
    class Program
    {
        static int[,] ships = new int[10, 10] {
            { 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, },
            { 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, },
            { 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, },
            { 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, },
            { 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, },
            { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, },
            { 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, },
            { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, },
            { 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, },
            { 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, }
        };

        // 深度优先搜索，沉没当前位置连通的所有舰船
        static void SinkShip(int x, int y)
        {
            // 超出边界或当前为水域直接返回
            if (x < 0 || x >= 10 || y < 0 || y >= 10 || ships[x, y] == 0)
                return;
            // 标记当前位置为已统计（沉没）
            ships[x, y] = 0;
            // 递归处理上下左右四个相邻位置
            SinkShip(x + 1, y);
            SinkShip(x - 1, y);
            SinkShip(x, y + 1);
            SinkShip(x, y - 1);
        }

        static void Main(string[] args)
        {
            int count = 0;

            // 遍历棋盘所有单元格
            for (int i = 0; i < 10; i++)
            {
                for (int j = 0; j < 10; j++)
                {
                    // 发现未统计的舰船
                    if (ships[i, j] == 1)
                    {
                        count++;
                        SinkShip(i, j);
                    }
                }
            }

            Console.WriteLine(count);
            Console.ReadLine();
        }
    }
}

输出结果 #

运行后输出8，即为正确的舰船总数。

内容的提问来源于stack exchange，提问作者Anastasia