原点から指定された円の円周上の任意の点に到達できるかどうかを確認します。

円の円周は、円の外側の境界として定義できます。円の円周です。円の周りのすべての点は、以下に示すような特定のプロパティに従います -

• 点 (x,y) は、$\mathrm{x^2 y^2

となる円の内側にあります。

• 点 (x,y) は、$\mathrm{x^2 y^2 = R^2}$

となるように円上に配置されます。

• 点 (x,y) は円の外側にあり、$\mathrm{x^2 y^2 > R^2}$

になります。

ここで、R = 円の半径。

＃＃＃問題文＃＃＃

一連の動き (L、R、U、D) を表す文字列 S と、円の半径を表す整数 R を与えます。 S から始まる一連の移動を選択して、原点を伴う半径 R の円周上の任意の点に到達できるかどうかを確認します。各動作の動作は次のとおりです。

L = x 座標を減らす

• #R = インクリメンタル x 座標

• U = y 座標の増分

• D = y 座標のデクリメント

• 例 1

  ＃＃＃＃＃＃入力＃＃＃＃＃＃ リーリー ＃＃＃＃＃＃出力＃＃＃＃＃＃ リーリー
イラスト

サブシーケンス「RR」を選択 -

最初は (0, 0) R -> (1, 0) R -> (2, 0) です。 周囲は 2

2

02 = 4 = R2

になります。

例 2

＃＃＃＃＃＃入力＃＃＃＃＃＃ リーリー ＃＃＃＃＃＃出力＃＃＃＃＃＃ リーリー

イラスト

最大のサブシーケンス「UUUU」を選択します -

最初は、(0, 0) U -> (0, 1) U -> (0, 2) U -> (0, 3) U -> (0, 4) U -> (0, 5) 。 0² 5

2

= 25 R

2

であるため、円周に到達することは不可能です。 方法 1: ブルート フォース クラッキング

この問題の解決策は、文字列 S の考えられるすべての部分列を見つけて、各部分列が円に到達できるかどうかを確認することです。これらの条件は、x と y のカウンターを維持することによってチェックされます。ここで、x は L ごとに減分され、R ごとに増分されます。同様に、y は D ごとに減少し、U ごとに増加します。次に、x2 y

2

= R

2

をチェックして、終点が円周上にあるかどうかを確認します。

疑似コード

リーリー

例: C 実装 次のプログラムでは、文字列 S の可能なすべての部分列を作成し、それらが円周に達するかどうかを確認します。 ^{リーリー ＃＃＃出力＃＃＃ リーリー} 方法 2: 最適化方法 この問題を解決する効率的な方法は、(L、R、U、または D) を使用して、x と y の二乗の合計が x と y の任意のペアの半径の二乗に等しいかどうかを確認することです。

まず、各ステップの最大出現数を数え、それらのいずれかが R に等しいかどうかを確認します。等しくない場合は、任意の数の L または R と U または D のペアによって距離原点が R に等しくなるかどうかを確認します。

疑似コード ^リーリー 以下は C 実装です。 次のプログラムでは、マップを使用して、円の円周につながる部分列があるかどうかを確認します。 ^{リーリー ＃＃＃出力＃＃＃ リーリー ＃＃＃結論は＃＃＃} 要約すると、文字列 S の一連のステップを使用して原点を中心とする円の円周を取得できるかどうかを確認するには、上記の方法のいずれかを使用できます。 2 番目の方法は高速な方法ですが、余分なスペースを使用します。一方、1 番目の方法は、あまり効率的ではありませんが、理解しやすい強引な方法です。

以上が原点から指定された円の円周上の任意の点に到達できるかどうかを確認します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。