题目链接

题意

给出一个n*m的地图，还有一个操作序列，你原本是要按照序列执行操作的，但是你可以修改操作：删除某些操作或者增加某些操作，问从'R'到'E'最少需要多少次修改操作。

思路

和上次比赛做的一道字符串题目有点类似。

定义状态dp[x][y][d]代表在(x,y)这个点执行到了第d个操作。因此有三种情况：不变，增加，删除。

1. 不变：就按照原来的序列走，如果走到不合法，就原地不动。转移：dp[x][y][d] = min（dp[x][y][d], dp[nx][ny][d+1]）。

2. 其实增加和删除操作是一样的，因为删除操作就相当于你执行走到另一个点，然后增加一个操作，走回来，因此可以一起讨论为增加操作。转移：dp[x][y][d] = min（dp[x][y][d], dp[nx][ny][d]）。注意这里的d是不变的，因为只是增加操作，并不影响原来的操作序列。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef pair<int, int> pii;

const int INF = 0x3f3f3f3f;

const int N = 50 + 11;

struct Node {

	int x, y, d;

	Node () {}

	Node (int _x, int _y, int _d) : x(_x), y(_y), d(_d) {}

} ;

char mp[N][N], s[N];

int dp[N][N][2*N], dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};

map<char, int> ying;

queue<Node> que;

int main() {

	int n, m;

	scanf("%d%d", &n, &m);

	for(int i = 1; i <= n; i++) scanf(" %s", mp[i] + 1);

	int sx, sy, ex, ey;

	for(int i = 1; i <= n; i++)

		for(int j = 1; j <= m; j++)

			if(mp[i][j] == 'R') sx = i, sy = j;

			else if(mp[i][j] == 'E') ex = i, ey = j;

	scanf(" %s", s + 1);

	int len = strlen(s + 1);

	ying['D'] = 0, ying['U'] = 1, ying['R'] = 2, ying['L'] = 3;

	memset(dp, INF, sizeof(dp));

	Node now = Node(sx, sy, 1);

	que.push(now); dp[sx][sy][1] = 0;

	int dep = 0;

	while(!que.empty()) {

		now = que.front(); que.pop();

		int x = now.x, y = now.y, d = now.d, nx, ny, nd;

		if(d > dep) dep = d;

		if(d <= len) {

			int c = ying[s[d]];

			nx = x + dx[c], ny = y + dy[c], nd = d + 1;

			if(nx < 1 || nx > n || ny < 1 || ny > m || mp[nx][ny] == '#') nx = x, ny = y;

			if(dp[nx][ny][nd] > dp[x][y][d])

				dp[nx][ny][nd] = dp[x][y][d], que.push(Node(nx, ny, nd));

		}

		for(int c = 0; c < 4; c++) {

			nx = x + dx[c], ny = y + dy[c], nd = d;

			if(nx < 1 || nx > n || ny < 1 || ny > m || mp[nx][ny] == '#') nx = x, ny = y;

			if(dp[nx][ny][nd] > dp[x][y][d] + 1)

				dp[nx][ny][nd] = dp[x][y][d] + 1, que.push(Node(nx, ny, nd));

		}

	}

	int ans = INF;

	for(int i = 1; i <= dep; i++) ans = ans > dp[ex][ey][i] ? dp[ex][ey][i] : ans;

	printf("%d\n", ans);

}