欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

hdu 1078

程序员文章站 2022-04-15 20:13:22
思路:能够向四个方向前进,同时前进步数不超过m。那么,在遍历的时候运用一层循环将不超过m步的都一一列举出来。    同时,在遍历的过程中需要记录数据形成记忆是搜索。 ......
 1 #include<iostream>
 2 #include<string.h>
 3 #include<algorithm>
 4 using namespace std;
 5 int A[150][150];
 6 int dp[150][150];
 7 int maxv=0;
 8 int n,m;
 9 int tr[4][2]= {{-1,0},{1,0},{0,-1},{0,1}};//上下左右
10 int Find(int x,int y)
11 {
12     if(dp[x][y]!=0) return dp[x][y];
13     for(int i=0; i<4; i++)
14     {
15         for(int j=1; j<=m; j++)
16         {
17             int x1,y1;
18             if(tr[i][0]==1)
19             {
20                 x1=x+j;
21                 y1=y;
22             }
23             if(tr[i][0]==-1)
24             {
25                 x1=x-j;
26                 y1=y;
27             }
28             if(tr[i][1]==-1)
29             {
30                 x1=x;
31                 y1=y-j;
32             }
33             if(tr[i][1]==1)
34             {
35                 x1=x;
36                 y1=y+j;
37             }
38             if(x1>=1&&x1<=n&&y1>=1&&y1<=n&&A[x][y]<A[x1][y1])
39             {
40                 dp[x][y]=max(Find(x1,y1)+A[x1][y1],dp[x][y]);
41             }
42         }
43     }
44     return dp[x][y];
45 }
46 int main()
47 {
48 
49     while(cin>>n>>m)
50     {
51         maxv=0;
52         if(n==-1&&m==-1) break;
53         memset(dp,0,sizeof(dp));
54         memset(A,0,sizeof(A));
55         for(int i=1; i<=n; i++)
56         {
57             for(int j=1; j<=n; j++)
58             {
59                 cin>>A[i][j];
60             }
61         }
62         Find(1,1);
63         cout<<dp[1][1]+A[1][1]<<endl;
64     }
65 
66 }