UVA 10913 - Walking on a Grid （记忆化搜索）

题目链接~~>

做题感悟：开始不用标记数组把 dp 数组初始化一下用于标记但是这样因为初始化的原因就超时了，改为标记数组才过。

解题思路：记忆化搜索

                这题很明显，如果用递推的方法的话必定不好写，因为在一行里可以向左做可以向右走，这样就导致不好递推，如果用记忆化方法的话就很好写了，如果单纯的只向右和下的话可以用三维标记 dp[ i ] [ j ] [ k ] (代表到达第i行第 j 列经历了 k 个负数所得到的最优值) ，这里还可以向左走，so~> 必须必须加一维方向，标记是从哪个方向得到的，放置重复走 ，即： dp [ i ] [ j ] [ k ] [ d ]  代表到达第 i 行第 j 列出现了 k 个负数从方向 d 得到的最优解。

代码：

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<ctime>
     
    
   

    

     

    
    

     

      #include<fstream>
     
    
   

    

     

    
    

     

      #include<sstream>
     
    
   

    

     

    
    

     

      #include<stack>
     
    
   

    

     

    
    

     

      #include<cstring>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<cstdio>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      #define INT long long int
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      const INT INF = 999999999 ;
     
    
   

    

     

    
    

     

      const INT MY = 10  ;
     
    
   

    

     

    
    

     

      const INT MX = 75 + 5 ;
     
    
   

    

     

    
    

     

      INT n ,k ;
     
    
   

    

     

    
    

     

      bool vis[MX][MX][MY][MY] ;
     
    
   

    

     

    
    

     

      INT dp[MX][MX][MY][MY] ,g[MX][MX] ;
     
    
   

    

     

    
    

     

      INT dx[4]={1 ,0 ,0} ,dy[4]={0 ,-1 ,1} ;
     
    
   

    

     

    
    

     

      void input()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 for(INT i = 0 ;i < n ;i++)
     
    
   

    

     

    
    

     
 for(INT j = 0 ;j < n ;j++)
     
    
   

    

     

    
    

     
 scanf("%lld",&g[i][j]) ;
     
    
   

    

     

    
    

     
 memset(vis ,false ,sizeof(vis)) ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      INT DP_Memory(INT x ,INT y ,INT z ,INT d)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if(z > k)  return -INF ;
     
    
   

    

     

    
    

     
 if(x==n-1 && y == n-1)
     
    
   

    

     

    
    

     
 return   g[x][y] ;
     
    
   

    

     

    
    

     
 if(vis[x][y][z][d])
     
    
   

    

     

    
    

     
 return dp[x][y][z][d] ;
     
    
   

    

     

    
    

     

       vis[x][y][z][d] = true ;
     
    
   

    

     

    
    

     

       INT& ans = dp[x][y][z][d] ;
     
    
   

    

     

    
    

     

       ans = -INF ;
     
    
   

    

     

    
    

     
 for(INT t = 0 ;t < 3 ;t++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       INT sx = x + dx[t] ;
     
    
   

    

     

    
    

     

       INT sy = y + dy[t] ;
     
    
   

    

     

    
    

     
 if(d + t == 3)  continue ;
     
    
   

    

     

    
    

     
 if(sx >= 0 && sy >= 0 && sx < n && sy < n)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       INT mx = (g[sx][sy] < 0) ;
     
    
   

    

     

    
    

     

       INT my = DP_Memory(sx ,sy ,z+mx ,t) ;
     
    
   

    

     

    
    

     
 if(my != -INF)
     
    
   

    

     

    
    

     

       ans = max(my + g[x][y] ,ans) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return  ans ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int cse = 1 ;
     
    
   

    

     

    
    

     
 while(scanf("%lld%lld",&n ,&k) ,n+k)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       input() ;
     
    
   

    

     

    
    

     

       INT x = (g[0][0] < 0) ,ans = -INF ;
     
    
   

    

     

    
    

     

       ans = DP_Memory(0 ,0 ,x ,0) ;
     
    
   

    

     

    
    

     
 cout<<"Case "<<cse++<<": " ;
     
    
   

    

     

    
    

     
 if(ans != -INF)
     
    
   

    

     

    
    

     
 cout<<ans<<endl ;
     
    
   

    

     

    
    

     
 else cout<<"impossible"<<endl ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/38495243