Labyrinth（Dp）2014年百度之星 資格賽

Labyrinth

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) 

Total Submission(s): 519    Accepted Submission(s): 174 

Problem Description

度度熊是一隻喜歡探險的熊，一次偶然落進了一個m*n矩陣的迷宮，該迷宮隻能從矩陣左上角第一個方格開始走，隻有走到右上角的第一個格子才算走出迷宮，每一次隻能走一格，且隻能向上向下向右走以前沒有走過的格子，每一個格子中都有一些金币（或正或負，有可能遇到強盜攔路搶劫， 度度熊身上金币可以為負，需要給強盜寫欠條 ），度度熊剛開始時身上金币數為0，問度度熊走出迷宮時候身上最多有多少金币？

Input

輸入的第一行是一個整數T（T < 200），表示共有T組資料。 每組資料的第一行輸入兩個正整數m，n（m<=100，n<=100）。接下來的m行，每行n個整數，分别代表相應格子中能得到金币的數量，每個整數都大于等于-100且小于等于100。

Output

對于每組資料，首先需要輸出單獨一行”Case #?:”，其中問号處應填入目前的資料組數，組數從1開始計算。 每組測試資料輸出一行，輸出一個整數，代表根據最優的打法，你走到右上角時可以獲得的最大金币數目。

Sample Input

23 41 -1 1 02 -2 4 23 5 1 -902 21 11 1

Sample Output

Case #1:18Case #2:4

------------------------------------------------------------------------------------------------

傷不起，同學告訴我是搜尋，我用dfs+dp做了4個小時，答案正确，但一直逾時，各種剪枝都試了，也無法ac。

還是對dfs的時間複雜度掌握不牢。

dfs代碼如下：

#include<stdio.h>

long map[107][107],n,m;
int play[3][2]={1,0,0,1,-1,0};
struct
{
  long ans,step;     
}f[107][107];

void dfs(int x,int y)
{
     int i,dx,dy;
     for(i=0;i<3;i++)
     {
       dx=x+play[i][0];
       dy=y+play[i][1];
       if(dx>0 && dy>0 && dx<=m && dy<=n && f[x][y].ans+map[dx][dy]>f[dx][dy].ans && f[dx][dy].step>=f[x][y].step)
         {
          f[dx][dy].ans=f[x][y].ans+map[dx][dy];
          f[dx][dy].step=f[x][y].step+1;
          dfs(dx,dy);
         }
     }
}

main()
{
  int t;
  while(scanf("%d",&t)!=EOF)
    {
      int hi=1;
      while(t--)
      {
        int i,j,a,b;
        scanf("%d %d",&m,&n);
        for(i=1;i<=m;i++)
          for(j=1;j<=n;j++)
             {scanf("%d",&map[i][j]);f[i][j].ans=-101;f[i][j].step=9999999;}
        f[1][1].ans=map[1][1];
        f[1][1].step=0;
        dfs(1,1);
        printf("Case #%d:\n",hi++);
        printf("%ld\n",f[1][n].ans);
           
           
      }
    }
}
           

冷靜一下，其實100的迷宮不算大，也沒有複雜的元素幹擾，是不是考慮貪心？

嘗試貪心模拟測試資料，發現可以用dp。每一格的金錢數，必然從3個狀态轉移而來。

舉例：

1 -1 1 0

2 -2 4 2

3 5 1 -90

dp[i][j]代表了地圖上坐标為i，j的最多金錢數，那麼dp矩陣的第一列必然是1 3 6

因為第一列隻能自上而下的移動。如果隻考慮向右移動，第二列可能是0 1 11 對于這一列，有可能還存在往上或者往下移動的可能，那麼我就把所有可能全列舉出來，并取最大值。注意防止回頭走重複的路陷入死循環，程式裡我用了一個變量tmp來防止走回來。

題目先輸入m再輸入n着實煩，我還是改回來了。ac代碼：

#include<stdio.h>
int map[107][107],n,m,dp[107][107];
int max(int a,int b)
{
    if(a>b)return a;
    else return b;
}
void DP(int c)
{
  for(int i=1;i<=n;i++)//自上而下 
  {
    int tmp=dp[i][c-1]+map[i][c];// tmp是用來記錄從左邊來的值 
    dp[i][c]=max(dp[i][c],tmp);
    for(int j=i+1;j<=n;j++)
      {
        tmp=tmp+map[j][c];
        dp[j][c]=max(dp[j][c],tmp);
      }
  }
  for(int i=n;i>=1;i--)//自下而上 
  {
    int tmp=dp[i][c-1]+map[i][c];
    dp[i][c]=max(dp[i][c],tmp);
    for(int j=i-1;j>=1;j--)
      {
        tmp=tmp+map[j][c];
        dp[j][c]=max(dp[j][c],tmp);
      }
  }
}

main()
{
  int t;
  while(scanf("%d",&t)!=EOF)
    {
      int hi=1;
      while(t--)
      {
        int i,j,a,b;
        scanf("%d %d",&n,&m);
        for(i=1;i<=n;i++)
          for(j=1;j<=m;j++)
             {scanf("%d",&map[i][j]);dp[i][j]=-999999;}   
       dp[1][1]=map[1][1];       //初始化第一列 
       for(i=2;i<=n;i++)
          dp[i][1]=dp[i-1][1]+map[i][1]; 
       for(i=2;i<=m;i++)
          DP(i);
        printf("Case #%d:\n",hi++);
        printf("%d\n",dp[1][m]);
           
      }
    }
}