本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16191401.html

D2T4 机器人

题目

刚上初一的小纯特别喜欢机器人，这周末，她报名了学校的“小机器人俱乐部”，而进入俱乐部需要通过一场考试。

考试场地可以看作一个 n×mn \times m 的网格图，行从上往下标号为 1,…,n1, \dots, n，列从左往右标号为 1,…,m1, \dots , m。每个格子有三种可能：空地，障碍物，机器人（有且只有一个），分别用“.”、“*”、“R”表示。现在小纯需要控制机器人在考试场地上行走，她每秒可以发送一条指令，为“W”——往上走、“S”——往下走、“A”——往左走、“D”——往右走的其中之一。由于俱乐部的机器人是避障机器人，当机器人接收到一条指令的时候，如果即将到达的位置为障碍物，那么机器人将留在原地，否则机器人向对应方向走一步。如果其走出边界则考试失败（例如在第一行发送指令向上走）。

为了增加考试的难度，俱乐部提供的机器人的信号接收器都存在问题。换言之，对于小纯给出的每一条指令，机器人有可能接收到指令并执行，也有可能接收不到指令并保持不动。现在小纯提供了一个指令序列，她想知道，这个指令序列是否存在某些情况使得这个指令序列走出边界。

image

思路

对于每个格子，显然，我们越早到这个格子是越优的。

基于此，我们可以对第一个点入队，查找它通往上下左右点最早在哪里，跑个最短路即可。

最后用Dij+优先队列优化，如果跑出格子了就输出 YES。

代码

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
#include<bits/stdc++.h>
using namespace std;
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'
){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x
<<3)+(ch^48);ch=getchar();}return x*f;}
#define N 610
#define M 200010
//#define mo
struct node
{
	int x, y, z; 
	bool operator <(const node &A) const
	{
		return z>A.z; 
	}
}p; 
int n, m, i, j, k, T;
int dx[4]={-1, 1, 0, 0}; 
int dy[4]={0, 0, -1, 1}; 
char s[N][N], c[M]; 
int a[N][N], nxt[M][5], len; 
int ax, bx, cx, ex, sx, sy; 
int x, y, z, newx, newy, flg;  
priority_queue<node>q; 

void init()
{
	ax=bx=cx=ex=flg=i=j=k=len=m=n=newx=newy=sx=sy=x=y=z=0; 
	memset(a, -1, sizeof(a)); 
	memset(c, 0, sizeof(c)); 
	memset(s, 0, sizeof(s)); 
	memset(nxt, 0, sizeof(nxt)); 
	while(!q.empty())  q.pop(); 
}

signed main()
{
//	freopen("robot.in", "r", stdin);
//	freopen("robot.out", "w", stdout);
	T=read(); 
	while(T--)
	{
		init(); 
		scanf("%s", c+1); len=strlen(c+1); 
		n=read(); m=read(); 
		for(i=1; i<=n; ++i) 
		{
			scanf("%s", s[i]+1); 
			for(j=1; j<=m; ++j)
				if(s[i][j]=='R') sx=i, sy=j; 
		}
		ax=bx=cx=ex=0; 
		for(i=len; i>=0; --i)
		{
			nxt[i][0]=ax; nxt[i][1]=bx; 
			nxt[i][2]=cx; nxt[i][3]=ex; 
			if(c[i]=='W') ax=i; 
			if(c[i]=='S') bx=i; 
			if(c[i]=='A') cx=i; 
			if(c[i]=='D') ex=i; 
		}
//		for(i=0; i<=len; ++i)
//			printf("%d %d %d %d\n", nxt[i][0], nxt[i][1], nxt[i][2], nxt[i][3]); 
		p.x=sx; p.y=sy; p.z=0; 
		q.push(p); 
		while(!q.empty())
		{
			p=q.top(); q.pop(); 
			if(a[x=p.x][y=p.y]!=-1) continue; 
			a[x][y]=z=p.z; 
			for(i=0; i<4; ++i)
			{
				if(!nxt[z][i]) continue; 
				newx=x+dx[i]; 
				newy=y+dy[i]; 
				if(a[newx][newy]!=-1) continue; 
				if(s[newx][newy]=='*') continue; 
				if(newx<1 || newy<1 || newx>n || newy>m)
				{
					printf("YES\n"); flg=1; 
					break; 
				}
				p.x=newx; p.y=newy; p.z=nxt[z][i]; 
				q.push(p); 
			}
			if(flg) break; 
		}
//		for(i=1; i<=n; ++i, printf("\n")) 
//			for(j=1; j<=m; ++j) printf("%2d ", a[i][j]); 
		if(!flg) printf("NO\n"); 
	}
	return 0;
}

总结

这题思维难度中等，想起来有一定难度。

对于每个格子，我们要考虑其最优情况是怎样，想清这一点，就迎刃而解了。

多测队列要清空！我因此没了90分。