HDU 5067 Harry And Dig Machine
and HDU MACHINE dig
2023-09-11 14:15:28 时间
Harry And Dig Machine
Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 506764-bit integer IO format: %I64d Java class name: Main
As we all know, Harry Porter learns magic at Hogwarts School. However, learning magical knowledge alone is insufficient to become a great magician. Sometimes, Harry also has to gain knowledge from other certain subjects, such as language, mathematics, English, and even algorithm.
Dumbledore, the headmaster of Hogwarts, is planning to construct a new teaching building in his school. The area he selects can be considered as an n*m grid, some (but no more than ten) cells of which might contain stones. We should remove the stones there in order to save place for the teaching building. However, the stones might be useful, so we just move them to the top-left cell. Taking it into account that Harry learned how to operate dig machine in Lanxiang School several years ago, Dumbledore decides to let him do this job and wants it done as quickly as possible. Harry needs one unit time to move his dig machine from one cell to the adjacent one. Yet skilled as he is, it takes no time for him to move stones into or out of the dig machine, which is big enough to carry infinite stones. Given Harry and his dig machine at the top-left cell in the beginning, if he wants to optimize his work, what is the minimal time Harry needs to finish it?
Dumbledore, the headmaster of Hogwarts, is planning to construct a new teaching building in his school. The area he selects can be considered as an n*m grid, some (but no more than ten) cells of which might contain stones. We should remove the stones there in order to save place for the teaching building. However, the stones might be useful, so we just move them to the top-left cell. Taking it into account that Harry learned how to operate dig machine in Lanxiang School several years ago, Dumbledore decides to let him do this job and wants it done as quickly as possible. Harry needs one unit time to move his dig machine from one cell to the adjacent one. Yet skilled as he is, it takes no time for him to move stones into or out of the dig machine, which is big enough to carry infinite stones. Given Harry and his dig machine at the top-left cell in the beginning, if he wants to optimize his work, what is the minimal time Harry needs to finish it?
Input
They are sever test cases, you should process to the end of file.
For each test case, there are two integers n and m.(1≤n,m≤50).
The next n line, each line contains m integer. The j-th number of ith line a[i][j] means there are a[i][j] stones on the jth cell of the ith line.( 0≤a[i][j]≤100 , and no more than 10 of a[i][j] will be positive integer).
For each test case, there are two integers n and m.(1≤n,m≤50).
The next n line, each line contains m integer. The j-th number of ith line a[i][j] means there are a[i][j] stones on the jth cell of the ith line.( 0≤a[i][j]≤100 , and no more than 10 of a[i][j] will be positive integer).
Output
For each test case, just output one line that contains an integer indicate the minimal time that Harry can finish his job.
Sample Input
3 3 0 0 0 0 100 0 0 0 0 2 2 1 1 1 1
Sample Output
4 4
解题:TSP问题
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int INF = 0x3f3f3f3f; 4 const int maxn = 11; 5 int n,m,d[maxn][maxn],dp[1<<maxn][maxn],tot; 6 struct Point { 7 int x,y; 8 Point(int a = 0,int b = 0){ 9 x = a; 10 y = b; 11 } 12 } p[maxn]; 13 int calc(int a,int b){ 14 return abs(p[a].x - p[b].x) + abs(p[a].y - p[b].y); 15 } 16 int main() { 17 int tmp; 18 while(~scanf("%d%d",&n,&m)) { 19 tot = 1; 20 for(int i = 1; i <= n; ++i) 21 for(int j = 1; j <= m; ++j) { 22 scanf("%d",&tmp); 23 if(tmp) p[tot++] = Point(i,j); 24 } 25 p[0] = Point(1,1); 26 for(int i = 0; i < tot; ++i) 27 for(int j = i; j < tot; ++j) 28 d[i][j] = d[j][i] = calc(i,j); 29 memset(dp,0x3f,sizeof dp); 30 dp[1][0] = 0; 31 int s = (1<<tot); 32 for(int i = 1; i < s; ++i){ 33 for(int j = 0; j < tot; ++j){ 34 if(dp[i][j] == INF) continue; 35 for(int k = 0; k < tot; ++k){ 36 if(((i>>k)&1) == 0 && dp[i|(1<<k)][k] > dp[i][j] + d[j][k]) 37 dp[i|(1<<k)][k] = dp[i][j] + d[j][k]; 38 } 39 } 40 } 41 int ret = INF; 42 for(int i = 0; i < tot; ++i) 43 ret = min(dp[s-1][i] + d[i][0],ret); 44 printf("%d\n",ret); 45 } 46 return 0; 47 }
相关文章
- hdu 1029 Ignatius and the Princess IV
- HDU 1006 Tick and Tick 时钟指针问题
- HDU 1069 Monkey and Banana(动态规划)
- HDU 1006 Tick and Tick 时钟指针问题
- [Algorithm] 122. Best Time to Buy and Sell Stock II
- [GraphQL] Set variable and default value & alias
- [Vue @Component] Handle Errors and Loading with Vue Async Components
- [Vue] Create Vue.js Layout and Navigation with Nuxt.js
- Document Builder: how does document element and variable cooperate
- Relationship between variable and element
- atitit.抽奖活动插件组件设计--结构设计and 抽奖流程建模
- Atitit..文件上传组件选型and最佳实践总结(3)----断点续传控件的实现
- The big deffrence between ($(du * )) and $(du *)
- hdu 1028 Ignatius and the Princess III
- Saving HDU hdu
- HDU 1068 Girls and Boys(最大独立集合 = 顶点数 - 最大匹配数)
- ssh, maven and eclipse那些破事
- HDU 5066 Harry And Physical Teacher(物理题)
- HDU 1312:Red and Black
- 零基础如何入门渗透and黑客「web安全」