潜在的なラテン方陣を読み取り、それが有効なラテン方陣かどうかを判断するプログラムを作成しています。今、選択したリージョンが連続したリージョンかどうかを確認しようとしています。
潜在的なラテン スクエアと地域の場所が同時に読み込まれます。リージョン[0,1][0,2][1,1][1,2]は連続しているため、有効なリージョンになります。 到達できない[0,0][0,2][1,1][1,2]ため、連続または有効ではありません。[0,0]それらが連続しているかどうかはどうすればわかりますか？
あなたの質問は、さまざまなことに対して、少なくとも 2 つの簡単なチェックを提案しています。すべてのポイントが他のすべてのポイントから到達可能であることを確認したい場合は、[x、y] が [x - 1, y]、[x + 1, y] にリンクされているネットワーク内のノードとしてポイントを扱うことができます。 ]、[x, y - 1]、および [x, y + 1]。深さ優先検索を使用して、特定の開始ノードから到達可能なすべてのノードを見つけることができます。任意の開始ノードからこのような検索を行います。すべてのノードにアクセスすると、選択されたリージョンは連続しています。これは、別の背景から来る単なるフラッド フィルだと思います。
ラテン語の正方形の場合、隣接する領域は問題ありませんか?それとも、軸に沿った長方形が必要ですか? たとえば、隣接する領域に 3 つのポイントしかない場合、それでよろしいですか? 軸に沿った長方形をチェックする場合は、セット内の x と y の最大値と最小値を計算し、すべての組み合わせ [a、b] があることを確認します。ここで、Xmin <= a <= Xmax およびYmin <= b <= Ymax.
この問題に対する妥当なアプローチは、フラッド フィルアルゴリズムです。
基本的に、リージョン内の任意のポイントから開始し、そのリージョン内のすべての隣接ポイントをマークしてから、まだマークされていないリージョン内のすべての隣接ポイントをマークすることによって、開始ポイントに接続されている一連のロケーションを作成します。 . マークする新しいものがない場合、開始点を含む最大連続領域を見つけたことになります。リージョン全体でない場合、リージョンは連続していません。