首页 > ACM题库 > HDU-杭电 > HDU 1428 漫步校园-动态规划-[解题报告] C++
2013
12-10

HDU 1428 漫步校园-动态规划-[解题报告] C++

漫步校园

问题描述 :

LL最近沉迷于AC不能自拔,每天寝室、机房两点一线。由于长时间坐在电脑边,缺乏运动。他决定充分利用每次从寝室到机房的时间,在校园里散散步。整个HDU校园呈方形布局,可划分为n*n个小方格,代表各个区域。例如LL居住的18号宿舍位于校园的西北角,即方格(1,1)代表的地方,而机房所在的第三实验楼处于东南端的(n,n)。因有多条路线可以选择,LL希望每次的散步路线都不一样。另外,他考虑从A区域到B区域仅当存在一条从B到机房的路线比任何一条从A到机房的路线更近(否则可能永远都到不了机房了…)。现在他想知道的是,所有满足要求的路线一共有多少条。你能告诉他吗?

输入:

每组测试数据的第一行为n(2=<n<=50),接下来的n行每行有n个数,代表经过每个区域所花的时间t(0<t<=50)(由于寝室与机房均在三楼,故起点与终点也得费时)。

输出:

针对每组测试数据,输出总的路线数(小于2^63)。

样例输入:

3
1 2 3
1 2 3
1 2 3
3
1 1 1
1 1 1
1 1 1

样例输出:

1
6

无意中又做到了记忆化搜索咯,上次做了一道记忆化搜索的题目,这题与那题基本是一样的,不过这次自己一步一步敲出来的,感觉还是不错的,记录下来。今天已经1月5号咯,在宁波这边也有半年咯,不知道怎么说自己的感受,总是觉得有些疲惫的感觉,可能是快放假咯。路真是一步一步走出来的,实验室的各位都很有意思,不过明年就要实习咯,希望自己能更给力啊。

这题有两个过程,一个是求出从n,n点到其他各点之间的距离,这个使用了一下bfs,但是这个写法,以前也用过,就是不断更新可以变小的点,昨天无意中觉得这个思想和SPFA的思想倒是挺像的,具体我一下还没想出来,再考虑下,有知道的也可以和我说下啊,脑子感觉有些不太转。下面的dfs是用了记忆化搜索,以前一听到DP的思想,真是头疼,碰都不敢碰。上次无意看到一个题目,所以想了想,基本的思想就是把后面的走过的一些情况记录下来,当下次再次走到的时候,因为前面已经求过咯,所以可以直接给出。真是dp的思想,搜索的形式。

#include<iostream>
#include<queue>
using namespace std;
const int INF = 100000005;

struct node
{
    int x, y;
    long long num;     
};

int sign[4][2] = {1, 0, -1, 0, 0, 1, 0, -1}, n;
long long MapValue[52][52], dp[52][52];
int map[52][52];

void bfs() //bfs求机房到各点的最短距离 
{
    int i;
    node f1, f2;
    f1.x = n;
    f1.y = n;
    f1.num = map[n][n];
    queue<node> q;
    MapValue[n][n] = map[n][n];
    q.push(f1);
    
    while(!q.empty())
    {
         f1 = q.front();
         q.pop();
          
         for(i = 0; i < 4; ++i)
         {
             f2.x = f1.x + sign[i][0];
             f2.y = f1.y + sign[i][1];     
             if(f2.x > 0 && f2.y > 0 && f2.x <= n && f2.y <= n) 
             {
                 f2.num = f1.num + map[f2.x][f2.y];
                 if(f2.num < MapValue[f2.x][f2.y])
                 {
                       MapValue[f2.x][f2.y] = f2.num;
                       q.push(f2);      
                 }    
             }     
         }               
                      
    }  
}

long long dfs(int x, int y) //记忆化搜索 
{
     if(x == n && y == n) return 1;
     if(dp[x][y] != 0) return dp[x][y];
     int x1, y1;
     long long sum = 0;
     
     for(int i = 0; i < 4; ++i)
     {
          x1 = x+sign[i][0];
          y1 = y+sign[i][1];
          if(x1 >= 1 && y1 >= 1 && x1 <= n && y1 <= n) 
          {
              if(MapValue[x][y] > MapValue[x1][y1]) 
              {
                  sum+=dfs(x1, y1);
                  dp[x][y] = sum;
              }
          }      
     }  
     return sum;
}

int main()
{
    int i, j;
    
    while(cin>>n)
    {
        for(i = 1; i <= n; ++i)
        {
           for(j = 1; j <= n; ++j)
           {
               scanf("%d",&map[i][j]);
               MapValue[i][j] = INF;      
           }      
        }  
         
        bfs();
        memset(dp, 0, sizeof(dp));
        cout<<dfs(1, 1)<<endl;
                  
    }
    return 0;
}


解题报告转自:http://blog.csdn.net/dnf1990/article/details/8469084