首页 > 代码库 > hdoj 5092 Seam Carving 【树塔DP变形 + 路径输出】 【简单题】
hdoj 5092 Seam Carving 【树塔DP变形 + 路径输出】 【简单题】
Seam Carving
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 956 Accepted Submission(s): 382
Problem Description
Fish likes to take photo with his friends. Several days ago, he found that some pictures of him were damaged. The trouble is that there are some seams across the pictures. So he tried to repair these pictures. He scanned these pictures and stored them in his computer. He knew it is an effective way to carve the seams of the images He only knew that there is optical energy in every pixel. He learns the following principle of seam carving. Here seam carving refers to delete through horizontal or vertical line of pixels across the whole image to achieve image scaling effect. In order to maintain the characteristics of the image pixels to delete the importance of the image lines must be weakest. The importance of the pixel lines is determined in accordance with the type of scene images of different energy content. That is, the place with the more energy and the richer texture of the image should be retained. So the horizontal and vertical lines having the lowest energy are the object of inspection. By constantly deleting the low-energy line it can repair the image as the original scene.
For an original image G of m*n, where m and n are the row and column of the image respectively. Fish obtained the corresponding energy matrix A. He knew every time a seam with the lowest energy should be carved. That is, the line with the lowest sum of energy passing through the pixels along the line, which is a 8-connected path vertically or horizontally.
Here your task is to carve a pixel from the first row to the final row along the seam. We call such seam a vertical seam.
For an original image G of m*n, where m and n are the row and column of the image respectively. Fish obtained the corresponding energy matrix A. He knew every time a seam with the lowest energy should be carved. That is, the line with the lowest sum of energy passing through the pixels along the line, which is a 8-connected path vertically or horizontally.
Here your task is to carve a pixel from the first row to the final row along the seam. We call such seam a vertical seam.
Input
There several test cases. The first line of the input is an integer T, which is the number of test cases, 0<T<=30. Each case begins with two integers m, n, which are the row and column of the energy matrix of an image, (0<m,n<=100). Then on the next m line, there n integers.
Output
For each test case, print “Case #” on the first line, where # is the order number of the test case (starting with 1). Then print the column numbers of the energy matrix from the top to the bottom on the second line. If there are more than one such seams, just print the column number of the rightmost seam.
Sample Input
2 4 3 55 32 75 17 69 73 54 81 63 47 5 45 6 6 51 57 49 65 50 74 33 16 62 68 48 61 2 49 76 33 32 78 23 68 62 37 69 39 68 59 77 77 96 59 31 88 63 79 32 34
Sample Output
Case 1 2 1 1 2 Case 2 3 2 1 1 2 1
题意：给一个N*M的矩阵，让你用一条线 从第1行连到第N行（每行仅仅能选一个元素），要求这条线所经过的元素之和最小。
有下面规定——
1，若你选择了位置（i，j）的元素，那么下一行的元素你仅仅能选择（i+1。j-1）、（i+1。j）、（i+1，j+1）三个之中的一个（当然边界仅仅能选两个）。
2，若能够找到多条 路径上元素之和最小 的线，那么你要优先选择最右边的线。
3。最后从第一行開始 输出线上元素的纵坐标。
思路：就是树塔变形题嘛。在自底往上推最优值的过程中。设置数组记录前驱，最后选择最右边的线输出路径就可以。因为题目没有说清楚（可能是我英语太渣）在找线的过程中是否要优先选择最右边的元素，所以我在DP过程中选择从左到右一直更新前驱。
队友说DP难，没心情深挖。
没办法，仅仅好主修图论 + DP。 其他仅仅能辅修了o(╯□╰)o
AC代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct Node
{
int pos;
};
Node mark[110][110];//标记该位置是由 哪一位置得到的（自底往上）
int dp[110][110];
int N, M;
int k = 1;
void getMap()
{
for(int i = 1; i <= N; i++)
{
for(int j = 1; j <= M; j++)
scanf("%d", &dp[i][j]);
}
}
void solve()
{
int t;
for(int i = N-1; i >= 1; i--)
{
for(int j = 1; j <= M; j++)
{
if(j == 1)
{
t = min(dp[i+1][j], dp[i+1][j+1]);//找到最小值
dp[i][j] += t;
//从左到右更新 前驱
if(t == dp[i+1][j])
mark[i][j].pos = j;
if(t == dp[i+1][j+1])
mark[i][j].pos = j + 1;
}
else if(j == M)
{
t = min(dp[i+1][j], dp[i+1][j-1]);
dp[i][j] += t;
if(t == dp[i+1][j-1])
mark[i][j].pos = j - 1;
if(t == dp[i+1][j])
mark[i][j].pos = j;
}
else
{
int t = min(dp[i+1][j], min(dp[i+1][j-1], dp[i+1][j+1]));
dp[i][j] += t;
if(t == dp[i+1][j-1])
mark[i][j].pos = j-1;
if(t == dp[i+1][j])
mark[i][j].pos= j;
if(t == dp[i+1][j+1])
mark[i][j].pos = j+1;
}
}
}
int sx = 1;
int Max = dp[1][1];
for(int i = 2; i <= M; i++)
{
if(Max >= dp[1][i])//优先选择最右边的线
{
Max = dp[1][i];
sx = i;
}
}
printf("Case %d\n", k++);
printf("%d", sx);
int row = 1, cul = sx;//行号 列号
while(1)
{
if(row == N) break;
cul = mark[row][cul].pos;//下一列号
printf(" %d", cul);
row++;
}
printf("\n");
}
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
scanf("%d%d", &N, &M);
getMap();
solve();
}
return 0;
}
hdoj 5092 Seam Carving 【树塔DP变形 + 路径输出】 【简单题】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。