fork download
copy 
  1. #include <iostream>
  2. #include <map>
  3. using namespace std;
  4.  
  5. struct place{   //座標を格納する構造体
  6.     int w;      //幅
  7.     int h;      //高さ
  8.     bool operator<(const place& pl) const {
  9.         return (w==pl.w)?(h<pl.h):(w<pl.w);
  10.     }
  11. };
  12.  
  13. bool DiscoveryMap(map<place,int> memo,place element);
  14.                                 //mapに要素が含まれるか調べる
  15. int solve(place now, map<place,int> *memo);
  16.  
  17. int main()
  18. {
  19.     map<place,int> memo;//メモ化再帰用
  20.     int w,h;
  21.     int answer;
  22.     place goal;
  23.  
  24.     cin >> w >> h;
  25.  
  26.     goal.w = w;
  27.     goal.h = h;
  28.  
  29.     answer = solve(goal,&memo);
  30.     cout << answer;
  31.     return 0;
  32. }
  33.  
  34. int solve(place now, map<place,int> *memo)
  35. {
  36.     place next1 , next2;
  37.     if( now.w == 1 || now.h == 1 )  //座標が壁際であれば
  38.         return 1;                   //1を返す
  39.  
  40.     if( DiscoveryMap(*memo,now) )//メモの中にあれば
  41.         return (*memo)[now];    //その値を返す
  42.  
  43.     next1.w = now.w;
  44.     next1.h = now.h - 1;    //一個下の座標
  45.  
  46.     next2.w = now.w - 1;    //一個左の座標
  47.     next2.h = now.h;
  48.  
  49.     (*memo)[now] = solve(next1, memo) + solve(next2, memo);
  50.         //メモに答えを格納
  51.     return (*memo)[now];
  52. }
  53.  
  54. bool DiscoveryMap(map<place,int>memo,place element)
  55. {
  56.     auto ite = memo.find(element);
  57.     return ite != memo.end();
  58. }
Time limit exceeded #stdin #stdout 5s 4772KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Mauxh
language:
C++14 (gcc 8.3)
created:
12 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!