Posted on 2008-10-31 15:25
Hero 閱讀(206)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 // 1029 C++ Accepted 0.031 1 205 KB URAL
2
3 //太假了--不想多說什么了
4
5 #include <stdio.h>
6 #include <stdlib.h>
7 #include <string.h>
8
9 const int INF = 1000000000 ;
10
11 int data[110][550] ;
12 int dp[110][550] ;
13
14 struct PATH
15 {
16 int x ;
17 int y ;
18 };
19 struct PATH path[110][550] ;
20 struct PATH que[110*550] ;
21 int head, tail ;
22
23 int inn, inm ;
24
25 void path_in_que( int floor, int posi )
26 {
27 if( 1 == floor )
28 {
29 que[++head].x = floor ; que[head].y = posi ;
30 }
31 else
32 {
33 path_in_que( path[floor][posi].x, path[floor][posi].y ) ;
34 que[++head].x = floor ; que[head].y = posi ;
35 }
36 }
37
38 int main()
39 {
40 scanf( "%d %d", &inn, &inm ) ;
41 for( int i=1; i<=inn; i++ )
42 {
43 for( int j=1; j<=inm; j++ )
44 {
45 scanf( "%d", &data[i][j] ) ;
46 }
47 }//data input
48
49 for( int i=1; i<=inm; i++ )
50 {
51 dp[1][i] = data[1][i] ;
52 path[1][i].x = 1 ; path[1][i].y = i ;
53 }
54 for( int i=2; i<=inn; i++ )
55 {
56 for( int j=1; j<=inm; j++ )
57 {
58 dp[i][j] = dp[i-1][j] + data[i][j] ;
59 path[i][j].x = i-1 ; path[i][j].y = j ;
60 }
61 int cnt = 1 ;
62 while( cnt != 0 )
63 {
64 cnt = 0 ;
65 for( int j=2; j<=inm; j++ )
66 {
67 if( dp[i][j] > dp[i][j-1]+data[i][j] )
68 {
69 dp[i][j] = dp[i][j-1] + data[i][j] ;
70 path[i][j].x = i ; path[i][j].y = j-1 ;
71 cnt ++ ;
72 }
73 }
74 for( int j=inm-1; j>=1; j-- )
75 {
76 if( dp[i][j] > dp[i][j+1]+data[i][j] )
77 {
78 dp[i][j] = dp[i][j+1] + data[i][j] ;
79 path[i][j].x = i ; path[i][j].y = j+1 ;
80 cnt ++ ;
81 }
82 }
83 }
84 }//dp
85
86 int minval = INF ; int minposi ;
87 for( int i=1; i<=inm; i++ )
88 {
89 if( minval >= dp[inn][i] ) { minval = dp[inn][i] ; minposi = i ; }
90 }
91
92 head = tail = 0 ;
93 //path_in_que( inn, minposi ) ;
94
95 que[++head].x = inn, que[head].y = minposi ;
96 int lastx = inn ;
97 int lasty = minposi ;
98 while( true )
99 {
100 int tempx = lastx ; int tempy = lasty ;
101 if( lastx==path[tempx][tempy].x && lasty==path[tempx][tempy].y ) break ;
102 lastx = path[tempx][tempy].x ; lasty = path[tempx][tempy].y ;
103 que[++head].x = lastx ; que[head].y = lasty ;
104 }
105 for( tail=head; tail>=1; tail-- )
106 {
107 //if( que[tail].x == inn ) break ;
108 printf( "%d ", que[tail].y ) ;
109 }
110 printf( "\n" ) ;
111 //printf( "%d\n", que[tail].y ) ;
112 /*
113 char *blank = "" ; tail = 1 ;
114 for( tail=1; tail<=head; tail++ )
115 {
116 if( que[tail].x == inn ) break ;
117 printf( "%d ", que[tail].y ) ;
118 }
119 printf( "%d\n", que[tail].y ) ;
120 */
121 return 0 ;
122 }