首页 > 代码库 > hdu 5092 Seam Carving
hdu 5092 Seam Carving
这道题 我没看出来 他只可以往下走，我看到的 8-connected ；所以今天写一下如果是 8-connected 怎么解；
其实说白了这个就是从上到下走一条线到达最后一行的距离最小； 从Map【a】【b】 到Map【a】【b+1】 的距离是Map【a】【b+1】 以此类推：建图即可；
然后在加一个点0，和n+m+1 点这样在建立一下从 0 点到第一行的边，和最后一行到（n+m+1） 的边 求一个从0 到(n+m+1) 的最短路径就好了，
怎么维护最右侧?： Dijkstra 有 队列优化！多以我们可以再这个由下级队列里面 吧col 号也设置进去；这样就可以使答案的字典序最大，也就是最右侧：
代码.cpp
#include <cstdio>#include <cmath>#include <algorithm>#include <cstring>#include <cstdlib>#include <iostream>#include <set>#include <map>#include <vector>#include <queue>#include <string>using namespace std;int n,m;int mat[105][105];int dd[][2]={-1,1, -1,0, -1,-1, 0,1, 0,-1, 1,1, 1,0, 1,-1 };int ddd[][2]={1,-1,1,0,1,1};bool jude(int x,int y){ return x>=1&&x<=n&&y>=1&&y<=m;}int ID(int x,int y){ return (x-1)*m+y;}const int INF = 1000000000;const int maxn =10000+10;struct Edge { int from, to, dist,col; Edge(){} Edge(int from,int to,int dist,int col):from(from),to(to),dist(dist),col(col){}};struct HeapNode { int d, u , col; HeapNode(){} HeapNode(int d,int u,int col):d(d),u(u),col(col){} bool operator < (const HeapNode& rhs) const { if(d==rhs.d) return col<rhs.col; return d > rhs.d; }};struct Dijkstra { int n, m; vector<Edge> edges; vector<int> G[maxn]; bool done[maxn]; int d[maxn]; int p[maxn]; void init(int n) { this->n = n; for(int i = 0; i < n; i++) G[i].clear(); edges.clear(); } void AddEdge(int from, int to, int dist,int col) { edges.push_back(Edge(from, to, dist,col)); m = edges.size(); G[from].push_back(m-1); } void dijkstra(int s) { priority_queue<HeapNode> Q; for(int i = 0; i < n; i++) d[i] = INF; d[s] = 0; memset(done, 0, sizeof(done)); Q.push( HeapNode(0, s , 0)) ; while(!Q.empty()) { HeapNode x = Q.top(); Q.pop(); int u = x.u; if(done[u]) continue; done[u] = true; for(int i = 0; i < G[u].size(); i++) { Edge& e = edges[G[u][i]]; if(d[e.to] > d[u] + e.dist) { d[e.to] = d[u] + e.dist; p[e.to] = G[u][i]; Q.push(HeapNode(d[e.to], e.to, e.col)); } } } } void GetShortestPaths(int s, int & dist, vector<int>&paths) { dijkstra(s); for(int i = n-1; i <n; i++) { dist = d[i]; paths.clear(); int t = i; paths.push_back(t); while(t != s) { paths.push_back(edges[p[t]].col); t = edges[p[t]].from; } reverse(paths.begin(), paths.end()); } }};Dijkstra solver;vector <int> path;int main(){ int t,ca=1; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); solver.init(n*m+2); for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&mat[i][j]); for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) { for(int k=0;k<3;k++) { int x=i+ddd[k][0]; int y=j+ddd[k][1]; if(!jude(x,y)) continue; solver.AddEdge(ID(i,j),ID(x,y),mat[x][y],y); } // 上边有个dd 数组 （用dd数组 8-connected 然后K 变成上届8 就可以了 ） } for(int i=1;i<=m;i++) solver.AddEdge(0,ID(1,i),mat[1][i],i); for(int i=1;i<=m;i++) solver.AddEdge(ID(n,i),n*m+1,0,105); int dis=0; solver.GetShortestPaths(0,dis,path); printf("Case %d\n",ca++); for(int i=0;i<path.size()-2;i++) { if(i==0) printf("%d",path[i]); else printf(" %d",path[i]); } puts(""); } return 0;}
hdu 5092 Seam Carving
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。