uva116 - Unidirectional TSP(기억형 검색)

제목: uva116 - Unidirectional TSP(기억 검색)
제목 대의: 하나의 수조를 제시한 다음에 첫 번째 열에서 임의의 줄(i, 0)부터 갈 수 있다. 세 위치(i+1, 1)(i, 1), (i-1, 0)만 갈 수 있다. 그리고 여기서 첫 번째 줄과 마지막 줄이 연결되어 있음을 묵인한다. 바로 i+1 또는 i-1이 경계를 넘으면 다른 경계로 가는 것이다.마지막으로 사전 순서의 최소 경로를 출력합니다.
문제풀이 사고방식: 기억화 검색.dp【x】【y】 =Min( dp【x + dir【i】【0】】【y + dir【i】【0】】 + mat【x】【y】).
코드:

#include <cstdio>
#include <cstring>

const int N = 15;
const int M = 105;
const int INF = 0x3f3f3f3f;
const int dir[3][2] = {{0, 1}, {1, 1}, {-1, 1}};

int mat[N][M];
int f[N][M];
int path[N][M];
int n, m;

int Min (const int a, const int b) { return a < b ? a: b; }

void init () {

	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= m; j++) {
			f[i][j] = INF;
			path[i][j] = n;
		}
}

int dp (int x, int y) {

	int& ans = f[x][y];
	if (y == m)
		return ans = 0;
	if (ans != INF)
		return ans;
	int nx, ny;
	int temp;
	for (int i = 0; i < 3; i++) {

		nx = x + dir[i][0];
		ny = y + dir[i][1];
		if (nx == -1)
			nx = n - 1;
		if (nx == n)
			nx = 0;
		temp = dp(nx, ny) + mat[x][y]; 
		if (temp <= ans) {
			if (temp == ans)
				path[x][y] = Min (path[x][y], nx);
			else
				path[x][y] = nx;
			ans = temp;
		}
	}
	return ans;
}

void printf_ans (int x, int y) {

	if (y == m - 1)
		return;
	printf (" %d", path[x][y] + 1);
	printf_ans(path[x][y], y + 1);
}

int main () {

	while (scanf ("%d%d", &n, &m) != EOF) {

		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				scanf ("%d", &mat[i][j]);

		init();

		int ans = INF;
		int temp, r;
		for (int i = n - 1; i >= 0; i--) {
			temp = dp(i, 0);
			if (temp <= ans) {
				ans = temp;
				r = i;
			}
		}

		printf ("%d", r + 1);
		printf_ans(r, 0);
		printf ("
%d
", ans);
	}
	return 0;
}