0

我只是在学习矩阵和算法。我提出了一个我还无法解决的问题。问题是，

由整数值组成的矩阵

#[0 0 0 2 2]
#|1 1 7 2 2|
#|2 2 7 2 1|
#|2 1 7 4 4|
#|2 7 7 4 4|
#|4 6 6 0 4|
#|4 4 6 4 4|
#[4 4 6 4 4]

当几个相同的值连接在一起（水平或垂直）时定义一个区域例如上面的矩阵，我们可以找到以下区域

#[0 0 0 * *]
#|* * * * *|
#|* * * * *|
#|* * * * *|
#|* * * * *|
#|* * * * *|
#|* * * * *|
#[* * * * *]

#[* * * 2 2]
#|* * * 2 2|
#|* * * 2 *|
#|* * * * *|
#|* * * * *|
#|* * * * *|
#|* * * * *|
#[* * * * *]

#[* * * * *]
#|1 1 * * *|
#|* * * * *|
#|* * * * *|
#|* * * * *|
#|* * * * *|
#|* * * * *|
#[* * * * *]

问题在于实现函数“Find Count Element Of Biggest Area”，它找到最大的区域（由最多元素组成的区域），并返回该区域的元素数量。例如上面的矩阵，最大的面积是：

#[* * * * *]
#|* * * * *|
#|* * * * *|
#|* * * 4 4|
#|* * * 4 4|
#|* * * * 4|
#|* * * 4 4|
#[* * * 4 4]

因此该函数将返回 9（该区域由 9 个元素组成）。

请对这个问题有任何帮助，我该如何解决？最好的办法 ？

谢谢..

4

1 回答 1

0

好的！我忍不住做你的作业...

以下 C# 代码使用递归函数来计算给定矩阵单元的所有未访问邻居。主程序循环遍历所有行和列以找到具有相同内容的邻居数最多的单元格。

namespace akArrayCluster
{
    class Program
    {
        static void Main(string[] args)
        {
            int[,] a = new int[,] 
            {
                {0, 0, 0, 2, 2},
                {1, 1, 7, 2, 2},
                {2, 2, 7, 2, 1},
                {2, 1, 7, 4, 4},
                {2, 7, 7, 4, 4},
                {4, 6, 6, 0, 4},
                {4, 4, 6, 4, 4},
                {4, 4, 6, 4, 4}
            };
            int row;
            int col;
            int res = getBiggestArea(a, out row, out col);

            o("");
            o("Biggest area has " + res + " cells");
            o("Top-left cell is [" + row + ";" + col + "]");
        }

        static int getBiggestArea(int[,] a, out int row, out int col)
        {
            int opt = 0;
            int cnt;
            int rows = a.GetLength(0);
            int cols = a.GetLength(1);
            bool[,] visited = new bool[rows, cols];

            row = col = -1;

            for (int r = 0; r < rows; r++)
                for (int c = 0; c < cols; c++)
                {
                    setAllToFalse(visited, rows, cols);

                    cnt = getNeighbourCount(a[r, c], a, visited, r, c);
                    if (cnt > opt)
                    {
                        opt = cnt;
                        row = r;
                        col = c;
                    }
                }

            setAllToFalse(visited, rows, cols);   //  edited col --> cols
            getNeighbourCount(a[row, col], a, visited, row, col);
            showSolution(a, visited, rows, cols);

            return opt;
        }

        static void setAllToFalse(bool[,] v, int rows, int cols)
        {            
            for (int row = 0; row < rows; row++)
                for (int col = 0; col < cols; col++)
                    v[row, col] = false;
        }

        static void showSolution(int[,] a, bool[,] visited, int rows, int cols)
        {
            string s;

            o("");
            for (int row = 0; row < rows; row++)
            {
                s = "";
                for (int col = 0; col < cols; col++)
                {
                    s += " " + (visited[row, col] ? a[row, col].ToString() : ".");
                }

                o(s);
            }
        }

        static int getNeighbourCount(int ca, int[,] a, bool[,] visited, 
                                     int row, int col)
        {
            int nc = 0;
            int rows = a.GetLength(0);
            int cols = a.GetLength(1);

            if ((row >= 0) && (row < rows) && 
                (col >= 0) && (col < cols) && 
                (ca == a[row, col]) && !visited[row, col])
            {
                visited[row, col] = true;

                nc = 1
                    + getNeighbourCount(ca, a, visited, row, col - 1)
                    + getNeighbourCount(ca, a, visited, row - 1, col)
                    + getNeighbourCount(ca, a, visited, row, col + 1)
                    + getNeighbourCount(ca, a, visited, row + 1, col);
            }

            return nc;
        }

        static void o(string s)
        {
            System.Console.WriteLine(s);
        }
    }
}

运行程序的结果：

 . . . . .
 . . . . .
 . . . . .
 . . . 4 4
 . . . 4 4
 . . . . 4
 . . . 4 4
 . . . 4 4

Biggest area has 9 cells
Top-left cell is [3;3]

第二个例子（参见下面的评论）：

 . 2 2 2 2
 2 2 2 2 2
 . . . 2 2
 . . . . 2

Biggest area has 12 cells
Top-left cell is [0;1]
于 2013-02-23T12:02:35.743 回答