生活随笔
收集整理的这篇文章主要介绍了
2021.04.14HDOJ
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
猫和老鼠（4）
Sample Input
3 1
1 2 5
10 11 6
12 12 7
-1 -1
Sample Output
37
#include <bits/stdc++.h>
using namespace std
;
const int maxn
=110;
int dp
[maxn
][maxn
];
int g
[maxn
][maxn
];
int n
,k
;
int dfs(int x
,int y
){if(dp
[x
][y
]) return dp
[x
][y
];dp
[x
][y
]=g
[x
][y
];for(int i
=1; i
<=k
; i
++){if(x
+i
<=n
-1&&g
[x
+i
][y
]>g
[x
][y
]){dp
[x
][y
]=max(dp
[x
][y
],g
[x
][y
]+dfs(x
+i
,y
));}if(x
-i
>=0&&g
[x
-i
][y
]>g
[x
][y
]){dp
[x
][y
]=max(dp
[x
][y
],g
[x
][y
]+dfs(x
-i
,y
));}if(y
+i
<=n
-1&&g
[x
][y
+i
]>g
[x
][y
]){dp
[x
][y
]=max(dp
[x
][y
],g
[x
][y
]+dfs(x
,y
+i
));}if(y
-i
>=0&&g
[x
][y
-i
]>g
[x
][y
]){dp
[x
][y
]=max(dp
[x
][y
],g
[x
][y
]+dfs(x
,y
-i
));}}return dp
[x
][y
];
}
int main()
{while(cin
>>n
>>k
){if(n
==-1&&k
==-1) break;memset(dp
,0,sizeof(dp
)); for(int i
=0; i
<n
; i
++){for(int j
=0; j
<n
; j
++){cin
>>g
[i
][j
];}}dfs(0,0);cout
<<dp
[0][0]<<endl
;}return 0;
}
#include <bits/stdc++.h>
using namespace std
;
const int maxn
=110;
int dp
[maxn
][maxn
];
int g
[maxn
][maxn
];
int n
,k
;
int dx
[]={1,0,-1,0},dy
[]={0,1,0,-1};
int dfs(int x
,int y
){if(dp
[x
][y
]) return dp
[x
][y
];int ans
=0;for(int i
=0; i
<4; i
++){for(int j
=1; j
<=k
; j
++){int nx
=x
+dx
[i
]*j
,ny
=y
+dy
[i
]*j
; if(0<=nx
&&nx
<=n
-1&&0<=ny
&&ny
<=n
-1&&g
[nx
][ny
]>g
[x
][y
]){ans
=max(ans
,dfs(nx
,ny
));}}}dp
[x
][y
]=g
[x
][y
]+ans
;return dp
[x
][y
];
}
int main()
{while(cin
>>n
>>k
){if(n
==-1&&k
==-1) break;memset(dp
,0,sizeof(dp
));for(int i
=0; i
<n
; i
++){for(int j
=0; j
<n
; j
++){cin
>>g
[i
][j
];}}dfs(0,0);cout
<<dp
[0][0]<<endl
;}return 0;
}
How many ways
Sample Input
1
6 6
4 5 6 6 4 3
2 2 3 1 7 2
1 1 4 6 2 7
5 8 4 3 9 5
7 6 6 2 1 5
3 1 1 3 7 2
Sample Output
3948
#include <bits/stdc++.h>
using namespace std
;
const int maxn
=110;
int g
[maxn
][maxn
];
int n
,m
;
int dp
[maxn
][maxn
];
int dfs(int x
,int y
){if(dp
[x
][y
]!=-1) return dp
[x
][y
];dp
[x
][y
]=0;for(int i
=0; i
<=g
[x
][y
]; i
++){for(int j
=0; j
<=g
[x
][y
]-i
; j
++){ if(x
+i
>=1&&x
+i
<=n
&&y
+j
>=0&&y
+j
<=m
){dp
[x
][y
]=(dp
[x
][y
]+dfs(x
+i
,y
+j
))%10000;}}}return dp
[x
][y
];
}
int main(){ios
::sync_with_stdio(0); cin
.tie(0); cout
.tie(0);int T
; cin
>>T
;while(T
--){cin
>>n
>>m
;memset(dp
,-1,sizeof(dp
)); for(int i
=1; i
<=n
; i
++){for(int j
=1; j
<=m
; j
++){cin
>>g
[i
][j
];}}dp
[n
][m
]=1;dfs(1,1);cout
<<dp
[1][1]<<endl
;}return 0;
}
总结
以上是生活随笔为你收集整理的2021.04.14HDOJ的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
