POJ 2353 Ministry(양방향 DP)

1272 단어
/*
  :  M*N,  :    、  、   ,                 。

  :  DP(      for  ),            、  、  ,           
    Dijskra          ,    !
*/

#include <cstdio>
#include <cstring>
const int mMax = 107;
const int nMax = 507;
int map[mMax][nMax];
__int64 d[nMax];
int dir[mMax][nMax];
int M, N;

void print(int x, int y)
{
	if(dir[x][y] == 0)
		print(x - 1, y);
	else if(dir[x][y] == 1)
		print(x, y - 1);
	else if(dir[x][y] == 2)
		print(x, y + 1);
	printf("%d
", y + 1); } int main() { while(scanf("%d%d", &M, &N) != EOF) { int i, j; for(i = 0; i < M; ++ i) { for(j = 0; j < N; ++ j) scanf("%d", &map[i][j]); } for(j = 0; j < N; ++ j) d[j] = map[0][j], dir[0][j] = -1; for(i = 1; i < M; ++ i) { for(j = 0; j < N; ++ j) d[j] = d[j] + map[i][j], dir[i][j] = 0; for(j = 1; j < N; ++ j) { if(d[j] > d[j - 1] + map[i][j]) d[j] = d[j - 1] + map[i][j], dir[i][j] = 1; } for(j = N - 2; j >= 0; -- j) { if(d[j] > d[j + 1] + map[i][j]) d[j] = d[j + 1] + map[i][j], dir[i][j] = 2; } } int _max = 0; for(j = 1; j < N; ++ j) { if(d[j] < d[_max]) _max = j; } print(M - 1, _max); } return 0; }

좋은 웹페이지 즐겨찾기