2016-2017 ACM-ICPC Pacific Northwest Regional Contest (Div. 1) Buggy Robot

2016-2017 ACM-ICPC Pacific Northwest Regional Contest (Div. 1) Buggy Robot

七月 30, 2021

题目概述

有个机器人在一个网格中靠执行一串LRUD指令行动，但这串指令有问题，并不能保证机器人一定能从起点走到终点。当机器人执行一条指令可能出界或遇到障碍，则相当于这条指令无效。而一旦机器人到达了终点，则之后未执行的指令都不用执行。现在问在原串上最少增添多少条指令，可以使机器人从起点到达终点。

数据范围

分析与解

看到字符串就想匹配，有些狭隘了。确实有匹配的因素，但我们关心的是从一个字符到下一个字符的转移，而并非事先构造出整个串。其实我们并不关心具体增添那些指令，只关心最小增添的个数。而增添的情形，实际上是由坐标来决定的。

因此我们记$dp[i][j][k]$表示当前机器人位于$(i,j)$，即将执行第$k$​条指令时，​达到此状态最小的增添指令次数。那么其实还是枚举四个方向的情形，如果恰好枚举的方向和指令方向一致的话，就去更新$(i’,j’,k+1)$状态的dp值，否则相当于到了下一个点还是执行第$k$条指令。

复杂度为$O(nmk)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>
using namespace std;
char mp[55][55],cmd[55];
int dp[55][55][55];
const int INF = 0x3f3f3f3f;
int n,m,ans,len;
struct node {
	int x,y,k;
};
queue<node> Q;
bool check(int x,int y) {
	if((x>=1) && (x<=n) && (y>=1) && (y<=m) && mp[x][y]!='#')return true;
	return false;
}
int num(char c) {
	if(c=='L')return 0;
	if(c=='R')return 1;
	if(c=='U')return 2;
	if(c=='D')return 3;
}
void BFS() {
	int dx[4]= {0,0,-1,1};
	int dy[4]= {-1,1,0,0}; //rows & cols
	node now,nxt;
	int cmd_go;
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			if(mp[i][j]=='R') {
				Q.push({
					i,j,1
				});
				dp[i][j][1]=0;  //字符串标号 
				break;
			}
	while(!Q.empty()) {
		now=Q.front();
		Q.pop();
//		printf("%d %d %d val=%d\n",now.x,now.y,now.k-1,dp[now.x][now.y][now.k]); 
//		system("PAUSE");
		if(mp[now.x][now.y]=='E') {
			ans=min(ans,dp[now.x][now.y][now.k]);  //可以不执行完既定的指令
			continue; //!
		}
		for(int i=0; i<4; i++) {
			nxt.x=now.x+dx[i];
			nxt.y=now.y+dy[i];
			if(now.k<=len)
				cmd_go=num(cmd[now.k]);
			else cmd_go=-1;
			if(!check(nxt.x,nxt.y)) {
				if(cmd_go==i) {
					if(dp[now.x][now.y][now.k+1] > dp[now.x][now.y][now.k]) { //This is an invalid direct.
						if(dp[now.x][now.y][now.k+1]==INF)
							Q.push({
							now.x,now.y,now.k+1
						});
						dp[now.x][now.y][now.k+1]=dp[now.x][now.y][now.k];
					}
				}
			} else {
				if(cmd_go==i) {
//					printf("??\n");
					if(dp[nxt.x][nxt.y][now.k+1] > dp[now.x][now.y][now.k]) { //No need to add new
						if(dp[nxt.x][nxt.y][now.k+1] == INF)
							Q.push( {
							nxt.x,nxt.y,now.k+1
						});
						dp[nxt.x][nxt.y][now.k+1]=dp[now.x][now.y][now.k];
					}
				} else {//Guaranteed that len will not be exceeded.
					if(dp[nxt.x][nxt.y][now.k] > dp[now.x][now.y][now.k] + 1) { //add new
						if(dp[nxt.x][nxt.y][now.k] == INF)
							Q.push( {
							nxt.x,nxt.y,now.k
						});
						dp[nxt.x][nxt.y][now.k]=dp[now.x][now.y][now.k] + 1;
					}
				}
			}
		}
	}
}
int main() {
//	freopen("B.in","r",stdin);
//	freopen("B-1.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++)scanf("%s",mp[i]+1);
	scanf("%s",cmd+1);
	len=strlen(cmd+1);
	memset(dp,63,sizeof(dp));
//	printf("%d\n",0x3f3f3f3f);
	ans=INF;
//	printf("%d %d\n",dp[0][0][0],ans);
	BFS();
	printf("%d\n",ans);
	return 0;
}