行列 (MXN) 内のセル (x,y) の位置を取り、行列のらせん順序トラバーサルでその位置 (1<=p<=M*N) を与える関数を見つけようとしています。例: M = 3、N = 3、および行列の場合:
[1,2,3]
[4,5,6]
[7,8,9]
スパイラル オーダー トラバーサルは : { 1,2,3,6,9,8,7,4,5 } を生成するため、関数が F(x,y) で示される場合、 :
F(1,1) = 1 、F(1,2) = 2、F(1,3) = 3、F(2,3) = 6 、.. など。
したがって、基本的には、特定の M、N、および位置 (x,y) に対して、スパイラル順序トラバーサルでそのセルの位置を生成する閉じた形式の式が必要です。
わかりました、解決策を考えました。テスト用のコードはまだ書いていませんが、仕事が終わって家に帰ったら、100% 確実にテストできると思います。
アルゴリズムで最初に行う必要があるのは、自分のポジションがどの四半期にあるかを把握することです。たとえば、マトリックスでは、マトリックスの中心はどの四半期にもありませんが、ポイントがどの軸上にあるかは常にわかります。一般的な考え方は、ポイントが側面からどれだけ離れているかを把握することです。そのため、探しているポイントに到達するまでにフルサーキットを何周する必要があるかを調べます。
辺からどれだけ離れているかを把握した後 (x と y と現在の四分の一と行列のサイズを取得するのは簡単なはずです)、この式を使用して、作成するトラバーサルで使用される位置の数を数えることができます。これらの回路。(nは側面からの距離)
sum = 2n * (M - 2n + N)
現在探しているポイントであるサーキットに到達するために使用されるポジションの数がある場合、唯一のことは、サーキット上でこのポイントからどれだけ離れているかを把握することです. 私たちは、私たちがどの四半期にいるかを知っていれば、簡単に数えられるはずだと思います.