1217.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1217 on 2006-07-23 at 15:16:23 */ 
#include <cstdio>
#include <cstring>

const int MAX = 128;
const int INF = 5000000;
const char STAT[][4] = { "LR", "LU", "LD", "UR", "UD", "UL", "RD", "RU", "DL", "DU", "DR" };
const int STAT_N = 22;

int cost(int, int, char);
int move(char, char);

int main()
{
	int i, j, k;
	int act[MAX][STAT_N], prev[MAX][STAT_N];
	char step[MAX];

	while(gets(step) != NULL && strcmp(step, "#")) {
		int l = strlen(step);
		for(i = 0; i <= l; i++)
			for(j = 0; j < STAT_N; j++) act[i][j] = INF;
		act[0][0] = act[0][1] = 0;
		for(i = 0; i < l; i++)
			for(j = 0; j < STAT_N; j++)
				for(k = 0; k < STAT_N; k++) {
					int p = cost(j, k, step[i]);
					if(act[i+1][k] > act[i][j] + p) {
						act[i+1][k] = act[i][j] + p;
						prev[i+1][k] = j;
					}
				}
		int o = 0;
		for(i = 0; i < STAT_N; i++)
			if(act[l][i] < act[l][o]) o = i;
		int next[MAX] = { 0 }, top = 0;
		for(i = l; i > 0; i--) {
			next[top++] = o;
			o = prev[i][o];
		}
		for(i = 0; top > 0; i++) {
			o = next[--top];
			if(cost(o, next[top+1], step[i]) == 0) putchar('.');
			else putchar("LR"[o&1]);
		}
		putchar('\n');
	}
	
	return 0;
}

int cost(int p, int c, char dir)
{
	int pd = p % 2, cd = c % 2;
	int ps = p / 2, cs = c / 2;
	if(dir == '.') {
		if(ps == cs) return 0;
		else {
			int min = INF, m;
			if((m = cost(p, c, 'L')) < min)  min = m;
			if((m = cost(p, c, 'R')) < min)  min = m;
			if((m = cost(p, c, 'U')) < min)  min = m;
			if((m = cost(p, c, 'D')) < min)  min = m;
			return min;
		}
	} else {
		int od = 1 - cd;
		if(STAT[cs][cd] != dir) return INF;
		if(STAT[ps][od] == "LR"[cd] && STAT[ps][cd] != dir) return INF;
		if(STAT[cs][od] != STAT[ps][od]) return INF;
		if(pd == od) return 1;
		else return move(STAT[ps][cd], STAT[cs][cd]);
	}
}
int move(char p, char c)
{
	if(p == c) return 3;
	else if(p+c == 'L'+'R' || p+c == 'U'+'D') return 7;
	else return 5;
}