algorithm - 任意の点のグリッドのトポロジカルソート？

Question

新しいポイントのx、y、またはその両方が大きい限り、1つのポイントからすぐに表示されるポイントに移動できるポイントx、yのグリッドがあります。これをトポロジ的に並べ替えるにはどうすればよいですか？

Answer 1

このグリッドには膨大な数のトポロジー順序があります。ただし、それらのいくつかは、スペースのオーバーヘッドなしで非常に簡単に計算できます。

1. 行を下から上、左から右に繰り返します。
2. 列を左から右、下から上に繰り返します。
3. x と y の合計が 0 である点、次に x と y の合計が 1 である点などをすべてリストします。

お役に立てれば！

Answer 2

これは推移的な関係であるため (つまり、a から b に、b から c に移動できる場合は、a から c に移動できる必要があります)、単純にポイントを並べ替えてトポロジカルな順序付けを行うことができます。

たとえば、次の C コードは、最初の座標に基づいてポイントを並べ替えるか、最初の座標が一致する場合は 2 番目の座標に基づいてポイントを並べ替えることにより、ポイントの配列のトポロジカル ソートを実行します。

int C[1000][2];

int compar(const void*a,const void*b)
{
  int *a2=(int*)a;
  int *b2=(int*)b;
  int d=a2[0]-b2[0];
  if (d)
    return d;  // Sort on first coordinate
  return a2[1]-b2[1];  // Sort on second coordinate
}

...
qsort(C,1000,sizeof(int)*2,compar);
...

あなたの例 (0,0) (1,99) (9,16) (16,9) (36,64) (64,36) (100,100) の場合、これらのポイントは最初の座標に従って既にソートされているので、これはqsort への呼び出しの出力になります。

このアプローチが機能するのは、a から b に移動できる場合、a の x が小さい (したがってリストの前に表示される) か、同じ x で y が小さい (また、ソートされたリストの前に表示される) 必要があるためです。