8

次の問題を解決しようとしていました。

平面格子の上を歩き回れる猿がいます。サルは一度に 1 マスずつ左、右、上、または下に移動できます。つまり、サルは (x, y) から (x+1, y)、(x-1, y)、(x, y+1)、(x, y-1) に移動できます。x 座標の絶対値の桁数の合計と y 座標の絶対値の桁数の合計が 19 以下である点は、サルがアクセスできます。たとえば、点 (59, 79) は、5 + 9 + 7 + 9 = 30 であり、19 よりも大きいため、アクセスできません。別の例: abs(-5) + であるため、点 (-5, -7) はアクセス可能です。 abs(-7) = 5 + 7 = 12、これは 19 未満です。サルが (0, 0) から開始した場合、(0, 0) 自体を含めて、サルはいくつのポイントにアクセスできますか?

次のブルート フォース ソリューション (疑似コード) を思いつきました。

/*
legitPoints = {}; // all the allowed points that monkey can goto
list.push( Point(0,0) ); // start exploring from origin

while(!list.empty()){
 Point p = list.pop_front(); // remove point

 // if p has been seen before; ignore p => continue;
 // else mark it and proceed further

 if(legit(p){
 // since we are only exploring points in one quadrant, 
 // we don't need to check for -x direction and -y direction
 // hence explore the following: this is like Breadth First Search
  list.push(Point(p.x+1, p.y)); // explore x+1, y
  list.push(Point(p.x, p.y+1)); // explore x, y+1

  legitPoints.insert(p); // during insertion, ignore duplicates 
                         // (although no duplicates should come through after above check)
                         // count properly using multipliers
                         // Origin => count once x = 0 && y == 0 => mul : 1
                         // X axis => count twice x = 0 && y != 0 => mul : 2
                         // Y axis => count twice x != 0 && y = 0 => mul : 2
                         // All others => mul : 4
 }

 return legitPoints.count();
}
*/

これは非常に強引な解決策です。私が使用した最適化の 1 つは、4 つではなく 1 つの象限を 1 回スキャンすることでした。もう 1 つは、これまで見てきた点を無視することでした。

しかし、最終的なポイントを見て、パターン、おそらく数学的解決策、または私が思いついたものよりも優れた別のアプローチを見つけようとしていました.

何かご意見は ？

PS: 必要に応じて、データをどこかに投稿できます。いずれかの軸を並べて見ると面白い。

第 1 象限ビジュアル: ここに画像の説明を入力

4

4 に答える 4

0

理想的な解決策を探すことなく、私は似たようなものを持っていました. サルがいるポイントごとに、次の 4 つの可能性をリストに追加し、それらが訪問されていない場合にのみ、次の 4 つに対して同じことを再帰的に行いました。これは、プロセスを高速化するためにマルチプロセッシングでも実行できます。

于 2013-08-08T19:26:04.267 に答える