パターンの動的プログラミング

codeeval.comのようなすばらしい週末サイトがあります。 小さなアルゴリズムの問​​題の良いコレクションと、楽しいプログラマーが楽しい夜を過ごすことができる便利な検証システムがあります。 通常、テストデータファイルが入力として使用されます。 しかし、テストデータが事前にわかっているという問題に遭遇しました。 単純に正しい答えを表示するプログラムをダウンロードすることはスポーティではありませんが、コンパイル段階で計算するのはまさにそれです。



この結果は内部で見ることができます。



タスク自体は複雑ではなく、非常に単純に再帰的に解決されます。 たとえば、次の関数を使用します。

int GetRouteCount(int map, int x, int y) { if ((x == -1) || (y == -1) || (x == 4) || (y == 4)) return 0; if ((x == 3) && ( y == 3)) return 1; if ( ( map & (1 << ( ( x << 2) +y) )) != 0 ) return 0; map |= (1 << ( (x << 2) +y)); return GetRouteCount(map, x-1, y) + GetRouteCount(map, x+1, y) + GetRouteCount(map, x, y-1) + GetRouteCount(map, x, y+1); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そして実際に結果を得る：

 int result = GetRouteCount(1, 0, 1) << 1;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次に、テンプレートで同じ計算を実行してみましょう。 テンプレートパラメータとして、動きの「マップ」と現在のポイントの座標を送信する必要があります。 ifの代わりにスペシャライゼーションが使用されるため、ポイント訪問を確認するには、このケースに特化した別のテンプレートを作成する必要があります。 メインテンプレートにもう1つのパラメーターを追加しようとすると、コンパイル段階で解決できない状況が発生します。 訪問チェックは次のようになります。

 template< template<int, int, int> class _MR, int map, int x, int y, bool visited> struct GetCount { enum Result { value = _MR<(map | (1 << ( ( x << 2) +y ))), (x-1), y>::value + _MR<(map | (1 << ( ( x << 2) +y ))), (x+1), y>::value + _MR<(map | (1 << ( ( x << 2) +y ))), x, (y-1)>::value + _MR<(map | (1 << ( ( x << 2) +y ))), x, (y+1)>::value }; }; template< template<int, int, int> class _MR, int map, int x, int y> struct GetCount<_MR, map, x, y, true> { enum Result { value = 0 }; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次に、グリッドを超える座標を専門とする基本テンプレートを作成し、目的地に到達したことを確認します。

 template <int map, int x, int y> struct MapRoute { enum Result { value = GetCount<MapRoute, map, x, y, ( (map & ( 1 << ( (x << 2) +y))) != 0 )>::value }; }; template<int map, int y> struct MapRoute<map, -1, y> { enum Result { value = 0 }; }; template<int map, int y> struct MapRoute<map, 4, y> { enum Result { value = 0 }; }; template<int map, int x> struct MapRoute<map, x, -1> { enum Result { value = 0 }; }; template<int map, int x> struct MapRoute<map, x, 4> { enum Result { value = 0 }; }; template<int map> struct MapRoute<map, 3, 3> { enum Result { value = 1 }; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

それだけです。結果を取得することは、実行時の計算と同じくらい簡潔に見えます。

 int result = MapRoute<0, 0, 0>::value;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

リンクをクリックすると、すべてのコードとその実行結果を表示できます。