Fotolog

A través del espejo
2010-10-12: A través del espejo
¡La radio habla en binario!
2010-10-10: ¡La radio habla en binario!
Gigaminx (regalo por mi cumple)
2010-09-16: Gigaminx (regalo por mi cumple)
Trini en bici
2010-09-05: Trini en bici
Valporquero
2010-08-28: Valporquero
Mi bici nueva
2010-08-22: Mi bici nueva
Boda de Mario y Ana
2010-08-13: Boda de Mario y Ana
De cañones en Guara
2010-08-07: De cañones en Guara
Trini y Mari en Marbella
2010-08-05: Trini y Mari en Marbella
Trini y Chelo en Tabarca
2010-08-03: Trini y Chelo en Tabarca
Valid XHTML 1.1
Acceder
Volver a la lista de problemas

Unidirectional TSP

116.c

#include <stdio.h>
#include <stdlib.h>

int tablero[100][100];
int dist[100][100];
int dir[100][100];
int m, n;

void
calc(void)
{
	int i,j;
	int min;
	int a;

	for(j=0; j<m; j++) {
		dist[j][n-1]=tablero[j][n-1];
	}

	for(i=n-2; i>=0; i--) {
		dist[0][i] = dist[0][i+1];
		dir[0][i] = 0;
		if (m>1) if (dist[1][i+1] < dist[0][i]) {
			dist[0][i] = dist[1][i+1];
			dir[0][i] = 1;
		}
		if (m>1) if (dist[m-1][i+1] < dist[0][i]) {
			dist[0][i] = dist[m-1][i+1];
			dir[0][i] = -1;
		}
		dist[0][i] += tablero[0][i];
		for(j=1; j<m-1; j++) {
			dist[j][i] = dist[j-1][i+1];
			dir[j][i] = -1;
			if (dist[j][i+1] < dist[j][i]) {
				dist[j][i] = dist[j][i+1];
				dir[j][i] = 0;
			}
			if (dist[(j+1)%m][i+1] < dist[j][i]) {
				dist[j][i] = dist[(j+1)%m][i+1];
				dir[j][i] = 1;
			}
			dist[j][i] += tablero[j][i];
		}
		dist[j][i] = dist[0][i+1];
		dir[j][i] = 1;
		if (dist[j-1][i+1] < dist[j][i]) {
			dist[j][i] = dist[j-1][i+1];
			dir[j][i] = -1;
		}
		if (dist[j][i+1] < dist[j][i]) {
			dist[j][i] = dist[j][i+1];
			dir[j][i] = 0;
		}
		dist[j][i] += tablero[j][i];
	}
	min=0;
	for(i=0; i<m; i++) {
		if (dist[i][0] < dist[min][0]) {
			min=i;
		}
	}
	printf("%d", min+1);
	a=min;
	for(i=1; i<n; i++) {
		a = (a+dir[a][i-1]+m)%m;
		printf(" %d", a+1);
	}
	printf("\n%d\n", dist[min][0]);
}

int
main(void)
{
	int i,j;

	while(1) {
		if (scanf("%d %d", &m, &n)!=2) {
			break;
		}
		if (m<1 || m>10 || n<1 || n>100) {
			abort();
		}
		for(i=0; i<m; i++) {
			for(j=0; j<n; j++) {
				if (scanf("%d", &tablero[i][j]) != 1) {
					abort();
				}
			}
		}
		calc();
	}
	exit(0);
}