0

私はマトリックスとアルゴリズムを学んでいます。私はまだ解決できなかった 1 つの質問にスタックします。質問は、

整数値で構成される行列

#[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
 . . . . 2

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