这道题正着推为什么会错？ WA:

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int M = 105, N = 30, Inf = 0x3f3f3f3f;
int n, m, s, t, tag[M][N], f[M][N], ans = Inf, rec, l;
char mark[M], front, g[M][N];
bool init() {
	memset(tag, 0, sizeof(tag));
	char tmp;
	for (int i = 1; i <= m; ++i)
		for (int j = 1; j <= n; ++j) {
			scanf(" %c", &tmp);
			if (tmp == 'O')
				tag[i][j] = 1;
		}
	scanf("%d%d", &s, &t);
	bool flag = 0;
	for (int i = s; i < t; ++i) {
		flag = 0;
		for (int j = 1; j <= n; ++j) {
			if (tag[i][j]) {
				flag = 1;
				break;
			}
		}
		if (!flag)return true;
	}
	return false;
}
void Work() {
	memset(f, 63, sizeof(f));
	memset(g, 0, sizeof(g));
	memset(mark, 0, sizeof(mark));
	for (int j = 1; j <= n; ++j) {
		if (tag[s][j])f[s][j] = 0;
		else f[s][j] = Inf;
	}
	for (int i = s + 1; i < t; ++i)
		for (int j = 1; j <= n; ++j) {
			f[i][j] = Inf;
			if (!tag[i][j])continue;
			for (int p = 1; p <= n; ++p)
				if (f[i][j] > f[i - 1][p] + (p != j) && tag[i - 1][p]) {
					f[i][j] = f[i - 1][p] + (p != j);
					g[i][j] = p;
				}
		}
	ans = Inf;
	rec = 0;
	for (int i = 1; i <= n; ++i) {
		if (ans > f[t - 1][i]) {
			ans = f[t - 1][i];
			rec = i;
		}
	}
	for (int i = t - 1; i >= s; --i) {
		mark[i] = rec + 'A' - 1;
		rec = g[i][rec];
	}
}
void print() {
	front = mark[s];
	l = s;
	for (int i = s + 1; i < t; ++i) {
		if (mark[i] != front) {
			printf("%c: %d-%d\n", front, l, i);
			l = i;
			front = mark[i];
		}
	}
	printf("%c: %d-%d", front, l, t);
}
int main() {
//		freopen("testin.txt", "r", stdin);
//		freopen("testout2.txt", "w", stdout);
	scanf("%d%d", &m, &n);
	for (int T = 1;; ++T) {
		if (m == 0 && n == 0)return 0;
		printf("Case %d:\n\n", T);
		if (init())
			printf("Not available");
		else {
			Work();
			print();
		}
		scanf("%d%d", &m, &n);
		if (m == 0 && n == 0)
			return 0;
		else putchar(10), putchar(10);
	}
	return 0;
}
/*
5 5
XOXOX
OXOXO
XOXOX
OXOXO
XOXOX
1 6
*/

AC:

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int M = 105, N = 30, Inf = 0x3f3f3f3f;
int n, m, s, t, tag[M][N], f[M][N], ans = Inf, rec, l;
char mark[M], front, g[M][N];
bool init() {
	memset(tag, 0, sizeof(tag));
	char tmp;
	for (int i = 1; i <= m; ++i)
		for (int j = 1; j <= n; ++j) {
			scanf(" %c", &tmp);
			if (tmp == 'O')
				tag[i][j] = 1;
		}
	scanf("%d%d", &s, &t);
	bool flag = 0;
	for (int i = s; i < t; ++i) {
		flag = 0;
		for (int j = 1; j <= n; ++j) {
			if (tag[i][j]) {
				flag = 1;
				break;
			}
		}
		if (!flag)return true;
	}
	return false;
}
void Work() {
	memset(f, 63, sizeof(f));
	memset(g, 0, sizeof(g));
	memset(mark, 0, sizeof(mark));
	for (int j = 1; j <= n; ++j) {
		if (tag[t-1][j])f[t-1][j] = 0;
		else f[t-1][j] = Inf;
	}
	for (int i = t - 2; i >= s; --i)
		for (int j = 1; j <= n; ++j) {
			f[i][j] = Inf;
			if (!tag[i][j])continue;
			for (int p = 1; p <= n; ++p)
				if (f[i][j] > f[i + 1][p] + (p != j) && tag[i + 1][p]) {
					f[i][j] = f[i + 1][p] + (p != j);
					g[i][j] = p;
				}
		}
	ans = Inf;
	rec = 0;
	for (int i = 1; i <= n; ++i) {
		if (ans > f[s][i]) {
			ans = f[s][i];
			rec = i;
		}
	}
	for (int i = s; i < t; ++i) {
		mark[i] = rec + 'A' - 1;
		rec = g[i][rec];
	}
}
void print() {
	front = mark[s];
	l = s;
	for (int i = s + 1; i < t; ++i) {
		if (mark[i] != front) {
			printf("%c: %d-%d\n", front, l, i);
			l = i;
			front = mark[i];
		}
	}
	printf("%c: %d-%d", front, l, t);
}
int main() {
	scanf("%d%d", &m, &n);
	for (int T = 1;; ++T) {
		if (m == 0 && n == 0)return 0;
		printf("Case %d:\n\n", T);
		if (init())
			printf("Not available");
		else {
			Work();
			print();
		}
		scanf("%d%d", &m, &n);
		if (m == 0 && n == 0)
			return 0;
		else putchar(10), putchar(10);
	}
	return 0;
}