黑马程序员技术交流社区

标题: 记忆化搜索 [打印本页]

---

作者: 善良的禽兽    时间: 2015-9-27 11:36
标题: 记忆化搜索

#include "cstdio"
#include "cmath"
#include "cstring"
#include "algorithm"
#include "iostream"
#include "vector"
#include "queue"
#include "stack"
#include "set"
#include "map"
#define lson root<<1
#define rson root<<1|1
#define lowbit(i) i&(-i)
#define debug(x) cout<<#x<<"="<<x<<endl;
#define here cout<<endl<<"_______________here "<<endl;
#define INF 0x7f7f7f7f
#define Prime 999983
#define N ***
using namespace std;

int flag[30][30][15];

int dp(int y, int x, int n)
{
           int sum(0);
           if(flag[y][x][n])
                 return flag[y][x][n];
      if(n == 0)
           return y == 15 && x == 15;      

      sum = dp(y - 1, x - 1, n - 1) + dp(y - 1, x, n - 1) + dp(y, x - 1, n - 1) + dp(y, x + 1, n - 1) + dp(y + 1, x, n - 1) + dp(y + 1, x + 1, n - 1);
      flag[y][x][n] = sum;
      return sum;
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    #endif
    int T, n;
    scanf("%d", &T);
    while(T--)
    {
             memset(flag, 0, sizeof(flag));
             scanf("%d", &n);
             flag[15][15][0] = 1;
             printf("%d\n",dp(15, 15, n));
    }
     return 0;
}//233ms

---

#include "cstdio"
#include "cmath"
#include "fstream"
#include "cstring"
#include "algorithm"
#include "iostream"
#include "vector"
#include "queue"
#include "stack"
#include "set"
#include "map"
#define lson root<<1
#define rson root<<1|1
#define lowbit(i) i&(-i)
#define debug(x) cout<<#x<<"="<<x<<endl;
#define here cout<<endl<<"_______________here "<<endl;
#define INF 0x7f7f7f7f
#define LINF 0x7f7f7f7f7f7f7f7f
#define Prime 999983
#define N 15
using namespace std;
long long dp[N][2 * N][2 * N];
int Move[6][2] = {{-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}};

bool judge(int posy, int posx)
{
           if(posy < 0 || posy > 2 * N || posx < 0 || posx > 2 * N)
                      return false;
           return true;
}

void Init()
{
          int posy, posx;
          memset(dp, 0, sizeof(dp));
     dp[0][N][N] = 1;
     for(int i = 1; i < N; i++)
     {
               for(int y = 0; y < 2 * N; y++)
               {
                        for(int x = 0; x < 2 * N; x++)
                        {
                                  for(int j = 0; j < 6; j++)
                                  {
                                             posy = y + Move[j][0];
                                             posx = x + Move[j][1];
                                             if(judge(posy, posx))
                                                   dp[y][x] += dp[i - 1][posy][posx];
                                  }
                        }
               }
     }      
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    #endif
    int T, n;
    Init();
    scanf("%d", &T);
    while(T--)
    {
             scanf("%d", &n);
             printf("%lld\n", dp[n][N][N]);
    }
    return 0;
}//0ms

---

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2