基于岛屿问题算法，修复C#连通'u'区域字符计数代码问题

已参考岛屿问题实现网格中'u'字符连通区域数量统计（Input1得2个、Input2得1个，结果正确），但CountLetterUInConnection方法无法统计每个连通区域内的'u'字符数量（如Input1的两个区域分别含22个和14个'u'）。要求禁止使用LINQ，需定位代码错误并给出正确实现。

输入输出示例 #

Input1 #

6×15网格
Output1:

2
22
14

Input2 #

对应网格
Output2:

1
5

现有代码 #

public partial class WebForm1 : System.Web.UI.Page
{
    protected void Page_Load(object sender, EventArgs e)
    {
        string path = "App_Data/Map.txt";
        string[] lines = File.ReadAllLines(HttpContext.Current.Server.MapPath(path));
        int Width = int.Parse(lines[0]);
        int Height = int.Parse(lines[1]);
        Label4.Text = "Width: " + Width.ToString();
        Label5.Text = "Height: " + Height.ToString();
        for (int i = 2; i < lines.Length; i++)
        {
            var newRow = new TableRow();
            var newCell = new TableCell();
            newCell.Text = lines[i];
            newRow.Cells.Add(newCell);
            Table1.Rows.Add(newRow);
        }
    }

    protected void Button1_Click(object sender, EventArgs e)
    {
        string path = "App_Data/Map.txt";
        string map = File.ReadAllText(HttpContext.Current.Server.MapPath(path));
        char[][] grid = GetGridGFromMap(map);
        int NumberOfMoles = TaskUtils.LettersIsU(grid);
        int Count = TaskUtils.CountLetterUInConnection(grid);
        // Label1.Text = "Cave count: " + NumberOfMoles.ToString();
        Label1.Text = Count.ToString();
    }

    protected void TextBox1_TextChanged(object sender, EventArgs e)
    {
    }

    protected void TextBox2_TextChanged(object sender, EventArgs e)
    {
    }
    
    private char[][] GetGridGFromMap(string map)
    {
        string[] lines = map.Split('\n');
        char[][] grid = new char[lines.Length][];
        for(int i =0; i < lines.Length; i++)
        {
            grid[i] = lines[i].ToCharArray();
        }
        return grid;
    }
}

class TaskUtils
{
    public static int LettersIsU(char[][] grid)
    {
        int count = 0;
        for (int i = 0; i < grid.Length; i++)
        {
            for (int j = 0; j < grid[i].Length; j++)
            {
                if (grid[i][j] == 'u')
                {
                    count++;
                    SetCountedLetters(grid, i, j);
                }
            }
        }
        return count;
    }
    
    private static void SetCountedLetters(char[][] grid, int i, int j)
    {
        if (i < 0 || i >= grid.Length || j < 0 || j >= grid[i].Length || grid[i][j] != 'u')
            return;
        grid[i][j] = 'z';
        SetCountedLetters(grid, i + 1, j);
        SetCountedLetters(grid, i - 1, j);
        SetCountedLetters(grid, i, j + 1);
        SetCountedLetters(grid, i, j - 1);
    }
    
    public static int CountLetterUInConnection(char[][] grid)
    {
        int count = 0;
        for (int i = 0; i < grid.Length; i++)
        {
            for (int j = 0; j < grid[i].Length; j++)
            {
                if (grid[i][j] == 'u')
                {
                    count++;
                    if ((i - 1 >= 0 && grid[i - 1][j] == 'u') || (i + 1 < grid.Length && grid[i + 1][j] == 'u')
                        || (j - 1 >= 0 && grid[i][j - 1] == 'u') || (j + 1 < grid[i].Length && grid[i][j + 1] == 'u'))
                    {
                        count++;
                    }
                }
            }
        }
        return count;
    }
}

错误分析 #

1. CountLetterUInConnection逻辑完全错误：该方法仅遍历每个'u'，每遇到一个'u'先+1，若周围有'u'再额外+1，这是无意义的重复计数，根本没有实现"遍历连通区域统计总'u'数"的逻辑。
2. 网格被篡改导致后续统计失效：LettersIsU方法会将遍历过的'u'改为'z'，但Button1_Click中先调用该方法修改原网格，后续调用CountLetterUInConnection时，原网格的'u'已被替换，无法正确统计。

正确实现方案 #

核心修改点 #

• 新增方法同时统计连通区域数量和每个区域的'u'数量，返回List<int>存储各区域大小，区域数量即为列表长度。
• 复制网格副本避免原数据被篡改，确保统计过程中数据的准确性。

修正后的完整代码 #

public partial class WebForm1 : System.Web.UI.Page
{
    protected void Page_Load(object sender, EventArgs e)
    {
        string path = "App_Data/Map.txt";
        string[] lines = File.ReadAllLines(HttpContext.Current.Server.MapPath(path));
        int Width = int.Parse(lines[0]);
        int Height = int.Parse(lines[1]);
        Label4.Text = "Width: " + Width.ToString();
        Label5.Text = "Height: " + Height.ToString();
        for (int i = 2; i < lines.Length; i++)
        {
            var newRow = new TableRow();
            var newCell = new TableCell();
            newCell.Text = lines[i];
            newRow.Cells.Add(newCell);
            Table1.Rows.Add(newRow);
        }
    }

    protected void Button1_Click(object sender, EventArgs e)
    {
        string path = "App_Data/Map.txt";
        string map = File.ReadAllText(HttpContext.Current.Server.MapPath(path));
        char[][] grid = GetGridGFromMap(map);
        // 获取每个连通区域的'u'数量列表
        List<int> regionSizes = TaskUtils.GetURegionSizes(grid);
        
        // 拼接结果：先输出区域数量，再依次输出每个区域的大小
        string result = regionSizes.Count.ToString() + "\n";
        foreach (int size in regionSizes)
        {
            result += size.ToString() + "\n";
        }
        // 去除末尾多余换行
        result = result.TrimEnd('\n');
        Label1.Text = result;
    }

    protected void TextBox1_TextChanged(object sender, EventArgs e)
    {
    }

    protected void TextBox2_TextChanged(object sender, EventArgs e)
    {
    }
    
    private char[][] GetGridGFromMap(string map)
    {
        string[] lines = map.Split('\n');
        char[][] grid = new char[lines.Length][];
        for(int i =0; i < lines.Length; i++)
        {
            grid[i] = lines[i].ToCharArray();
        }
        return grid;
    }
}

class TaskUtils
{
    // 统计所有'u'连通区域的大小，返回列表
    public static List<int> GetURegionSizes(char[][] grid)
    {
        List<int> sizes = new List<int>();
        // 创建网格副本，避免修改原数据
        char[][] gridCopy = CopyGrid(grid);
        
        for (int i = 0; i < gridCopy.Length; i++)
        {
            for (int j = 0; j < gridCopy[i].Length; j++)
            {
                if (gridCopy[i][j] == 'u')
                {
                    // 统计当前连通区域的'u'数量
                    int size = CountRegionSize(gridCopy, i, j);
                    sizes.Add(size);
                }
            }
        }
        return sizes;
    }
    
    // 深度优先遍历统计单个连通区域的大小
    private static int CountRegionSize(char[][] grid, int i, int j)
    {
        // 越界或不是'u'则返回0
        if (i < 0 || i >= grid.Length || j < 0 || j >= grid[i].Length || grid[i][j] != 'u')
        {
            return 0;
        }
        // 标记为已访问
        grid[i][j] = 'z';
        // 统计当前单元格+上下左右四个方向的数量
        return 1 + CountRegionSize(grid, i+1, j) + CountRegionSize(grid, i-1, j) + 
               CountRegionSize(grid, i, j+1) + CountRegionSize(grid, i, j-1);
    }
    
    // 复制二维字符数组，避免修改原网格
    private static char[][] CopyGrid(char[][] original)
    {
        char[][] copy = new char[original.Length][];
        for (int i = 0; i < original.Length; i++)
        {
            copy[i] = new char[original[i].Length];
            Array.Copy(original[i], copy[i], original[i].Length);
        }
        return copy;
    }
    
    // 保留原有的LettersIsU方法（如果需要单独统计区域数量）
    public static int LettersIsU(char[][] grid)
    {
        int count = 0;
        char[][] gridCopy = CopyGrid(grid);
        for (int i = 0; i < gridCopy.Length; i++)
        {
            for (int j = 0; j < gridCopy[i].Length; j++)
            {
                if (gridCopy[i][j] == 'u')
                {
                    count++;
                    SetCountedLetters(gridCopy, i, j);
                }
            }
        }
        return count;
    }
    
    private static void SetCountedLetters(char[][] grid, int i, int j)
    {
        if (i < 0 || i >= grid.Length || j < 0 || j >= grid[i].Length || grid[i][j] != 'u')
            return;
        grid[i][j] = 'z';
        SetCountedLetters(grid, i + 1, j);
        SetCountedLetters(grid, i - 1, j);
        SetCountedLetters(grid, i, j + 1);
        SetCountedLetters(grid, i, j - 1);
    }
}

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