2D配列のインデックス位置が「タッチする」

Question

2次元配列内の位置が「タッチしている」と同様の値で、まわりをトレースしている場合に返す方法を見つけることを検討しています。私がこれに入る前に、非常によく似た質問があり、解決されたのはhereですが、それは私が何も知っていないpythonで書かれています。さらに拡大するには、次の

f f f f 

f T T f 

f T T f 

f f f f 

彼らが戻って[0][0]に同じ値とチェーンをしているので、それがその配列内のすべてのfalsesを返します[0][0]から始まります。

f f f T f f f 

f T f T f T f 

f f f T f f f 

が、このいずれかに基づいて、[0][0]から始まることだけ[0][0,1,2]、[1][0,2]、および[2][0,1,2]を返します。しかし、[0][4]で始める場合は、[n][3]の後にすべての偽物を返します。なぜなら、開始値と同じ値で触れているからです。

私はコードを正確に書くのに役立つ人は探していませんが、正しい方向に向けることができます。私の初心者レベルを前もって言い訳してください、ありがとう！

Answer 1

あなたがグラフ問題を抱えているようだと、あなたは幅優先探索または同様のアルゴリズムを探しているところ

1. グラフノード：すべての有効な（f）配列項目
2. グラフエッジ：配列の項目が近傍の場合のみ

実装：

private static IEnumerable<Tuple<int, int>> Touching(char[,] items, 
                Tuple<int, int> startAt, 
                char letter = 'f') { 
    if (startAt.Item1 < 0 || startAt.Item1 >= items.GetLength(0) || 
     startAt.Item2 < 0 || startAt.Item2 >= items.GetLength(1)) 
    yield break; // or throw ArgumentOutOfRangeException 
    else if (items[startAt.Item1, startAt.Item2] != letter) 
    yield break; 

    Queue<Tuple<int, int>> agenda = new Queue<Tuple<int, int>>(); 
    HashSet<Tuple<int, int>> visited = new HashSet<Tuple<int, int>>() { startAt }; 

    agenda.Enqueue(startAt); 

    while (agenda.Any()) { 
    for (int i = agenda.Count - 1; i >= 0; --i) { 
     var point = agenda.Dequeue(); 

     yield return point; 

     // Manhattan: left, right, top, bottom neighbors only, no diagonal ones 
     var validNeighbors = new Tuple<int, int>[] { 
     new Tuple<int, int>(point.Item1 - 1, point.Item2),  // left 
     new Tuple<int, int>(point.Item1 + 1, point.Item2),  // right 
     new Tuple<int, int>(point.Item1, point.Item2 - 1),  // top 
     new Tuple<int, int>(point.Item1, point.Item2 + 1),} // bottom 
     .Where(p => p.Item1 >= 0 && p.Item1 < items.GetLength(0)) // Within array 
     .Where(p => p.Item2 >= 0 && p.Item2 < items.GetLength(1)) // Within array 
     .Where(p => items[p.Item1, p.Item2] == letter)   // valid point 
     .Where(p => visited.Add(p));        // not visited 

     foreach (var p in validNeighbors) 
     agenda.Enqueue(p); 
    } 
    } 
} 

テスト：

char[,] data = new char[,] { 
    { 'f', 'f', 'f', 'T', 'f', 'f', 'f',}, 
    { 'f', 'f', 'f', 'T', 'f', 'f', 'f',}, 
    { 'f', 'f', 'f', 'T', 'f', 'f', 'f',}, 
    }; 

    string report = string.Join(Environment.NewLine, 
    Touching(data, new Tuple<int, int>(0, 0), 'f')); 

    Console.WriteLine(report); 

アウトカム（以下、これらすべての項目がstartAtポイントからすなわち到達可能触れている - (0, 0)）：

(0, 0) 
(1, 0) 
(0, 1) 
(2, 0) 
(1, 1) 
(0, 2) 
(2, 1) 
(1, 2) 
(2, 2) 

のLINQの助けを借りて質問のようにさまざまな方法でレポートを整理できます：それはあなたが持っている問題の種類は明らかではありません

[0][0, 1, 2] 
[1][0, 1, 2] 
[2][0, 1, 2]