再帰処理からキューやスタックの処理にしたい

Question

今は再帰処理を使って、countで数え上げるプログラムです。
しかし、画像が少し大きくなるとStackOverflowExceptionを起こしてしまいます。
ソースコードは下記のとおりです。

int Expansion(int y, int x)
        {
            if ((x >= width) || (x < 0) || (y >= height) || (y < 0)) return 1;
            if (x < width && x >= 0 && y < height && y >= 0)
            {
                if (img.GetPixel(x, y) == Black)
                {
                    return 1;
                }
                else
                {
                    img.SetPixel(x, y, Black);
                    return (Expansion(y + 1, x) + Expansion(y - 1, x) +
                            Expansion(y + 1, x + 1) + Expansion(y - 1, x + 1) +
                            Expansion(y + 1, x - 1) + Expansion(y - 1, x - 1) +
                            Expansion(y, x + 1) + Expansion(y, x - 1));
                }
            }
            else return 1;
        }

この再帰処理をスタック、もしくはキューで書き換えたいです。
具体的なプログラムがあると、助かります。
何卒お力添えいただければ幸いです。

Answer 1

もともとのプログラムは、いって、もどって、いってを繰り返し、値が求まらない。
いわゆる無限ループになっている。
調べたところは戻らない。一方向にするというようにするために、
たどっていった履歴を残すことで、数え上げる。最後は、たどった履歴を数える。
C#7.0のローカル関数も使っています。
デバッグしていないので、バグあるかも。

//あらかじめ、白黒のデータをDicに突っ込んでおく。GetPixelは確か遅い。
        Dictionary<(int, int), bool> imageData = new Dictionary<(int, int), bool>();

        public int 連続を求める(int p_x,int p_y)
        { 
            HashSet<(int, int)> historyList = new HashSet<(int, int)>();
            Stack<(int, int)> stack = new Stack<(int, int)>();
            
            IEnumerable<(int,int)> 周辺の座標(int x,int y)
            {
                for (int i = -1; i <= 1; i++)
                {
                    for (int l = -1; l <= 1; l++)
                    {
                        yield return (x + i, y + l);
                    }
                }
            }

            void Check(int x,int y)
            {
                if (historyList.Contains((x, y)) == false && imageData.ContainsKey((x, y)))
                {
                    if (imageData[(x, y)])
                    {
                        historyList.Add((x, y));
                        foreach (var item in 周辺の座標( x,  y))
                        {
                            if (historyList.Contains(item) == false)
                            {
                                stack.Push(item);
                            }
                        }                        
                    }
                }
            }
            //開始地点の入力
            stack.Push((p_x, p_y));
            while(stack.Count>0)
            {
                var (x,y) = stack.Pop();
                Check(x,y);
            }
            return historyList.Count;
        }

Comments

[ponpo5555]

｢Expansion｣のところを｢連続を求める｣に置き換えるのですかね。
履歴を数えても、画素の連結成分の個数は求まらないような気がするのですが、
動かしてみても意図した答えになりません。

[kiichi54321]

「画素の連結成分の個数」は、同じ色でつながっているところを数え上げるってことじゃないの？

[ponpo5555]

例として、1が白、0が黒
1 1 1 0 0
1 1 0 0 1
1 0 0 0 0
0 0 1 1 0
連結成分の個数3つみたいなことです。

[kiichi54321]

historyList自体が島なんだから、この島が、何個作れるのか？と言うかたちにすればいいという感じですかね。

[ponpo5555]

そうですね...。

[ponpo5555]

無事数え上げることに成功しました！ありがとうございました！

Answer 2

Expansionを呼び出し過ぎなので、メモ化、Dictionaryにｘｙ座標に対する結果を格納するとかするといいのでは？
何度も同じ再帰を繰り返してしまうため、計算が無駄です。
動的計画法とかを勉強してみるといいと思います。

Dictonary<(int,int),int> dic = new Dictonary<(int,int),int>()
int Expansion(int y, int x)
        {
            if ((x >= width) || (x < 0) || (y >= height) || (y < 0)) return 1;
            if (dic.ContainKey((x,y)) return dic[(x,y)];
            if (x < width && x >= 0 && y < height && y >= 0)
            {
                var result = 1;
                if (img.GetPixel(x, y) != Black)
                {
                    img.SetPixel(x, y, Black);
                    result = (Expansion(y + 1, x) + Expansion(y - 1, x) +
                            Expansion(y + 1, x + 1) + Expansion(y - 1, x + 1) +
                            Expansion(y + 1, x - 1) + Expansion(y - 1, x - 1) +
                            Expansion(y, x + 1) + Expansion(y, x - 1));
                }
                dic.Add((x,y),result);
                return result;
            }
            else return 1;
        }

これなら座標分の計算しかしないので、スタックとかはとりあえず必要ないんじゃないかなぁ。

Comments

[kiichi54321]

ただ、これって、もともとのプログラムが、ほんとに「連結成分の個数を数える」ことができるのか謎だ。無限ループになっている感じがするし、2重３重に数え上げている感じがする。

[ponpo5555]

回答ありがとうございます。試してみたところ、
Dictionary<(int,int),int> dic = new Dictionary<(int,int),int>();
の部分が扱えませんでした。

[kiichi54321]

C#7.0　http://ufcpp.net/study/csharp/datatype/tuples/

[kiichi54321]

System.ValueTuple　を　nuget する

[ponpo5555]

度々申し訳ないです。
先ほどの部分は無事扱えることができました。
しかし、StackOverflowExceptionをまた起こしてしまいました。

[kiichi54321]

無限ループしているんだよ。