打卡信奥刷题（3629）用C++实现信奥题 P11864 「o.OI R1」α+β Problem-开发者社区

P11864 「o.OI R1」α+β Problem

题目背景

机器人小α\alphaα喜欢做游戏，机器人小β\betaβ喜欢玩游戏。

题目描述

现在，它们正在玩一个叫作推箱子的游戏！

机器人小β\betaβ为关卡制定了一个用字符串表示的移动路径：

字符	含义
`W`	让机器人前进一格
`S`	让机器人后退一格
`A`	让机器人左转
`D`	让机器人右转

身为机器人小α\alphaα，你需要构造一个n×mn\times mn×m的地图：

字符	含义
`\|`	机器人无法穿过的墙壁
`X`	机器人最开始在的位置
`S`	箱子最开始所在的位置
`.`	空地

注意每个位置的东西只能是以上四种之一。

机器人的初始位置是给定的，方向朝上，地图外都是墙。

小β\betaβ完成移动后，所有箱子都必须移动过，小α\alphaα需要让这个地图的箱子数最多，且小β\betaβ每步操作都合法。

以下给出所有不合法的操作：

操作	不合法情况
`W`	机器人前方是墙
`W`	机器人前方两格都是箱子
`W`	机器人前方两格分别是箱子和墙
`S`	机器人后方是箱子或墙

小α\alphaα需要一份程序来完成这份工作。

输入格式

本题有多组数据。

第一行一个正整数TTT表示数据组数。

对于每组数据：

第一行两个整数n,mn,mn,m。
第二行三个整数x,y,kx,y,kx,y,k。
第三行一个长度为kkk的字符串sss。

输入的数据含义如下：

nnn和mmm代表需要构造的地图的大小为nnn行mmm列。
xxx和yyy代表机器人的初始位置在从上往下第xxx行从左往右第yyy列。
kkk代表移动路径的长度，sss代表移动路径。

本题数据量较大，请使用较快的读写方式。

输出格式

对于每组数据，你需要给出一个n×mn\times mn×m的地图代表你构造的地图，格式如题目描述所述。

所有最优的答案都可以得分。

输入输出样例 #1

输入 #1

1 3 4 2 2 17 DWSAWDWSSDWAWDWAW

输出 #1

..S. SXS. ..S.

输入输出样例 #2

输入 #2

1 3 4 3 4 9 WSAWWDWDW

输出 #2

|.|. |SSS ..SX

输入输出样例 #3

输入 #3

1 3 4 2 1 8 DWASDWAW

输出 #3

||.| XS.| |.S.

输入输出样例 #4

输入 #4

2 5 4 5 1 9 WDWAWDWAW 5 19 5 8 12 DDSAADDADADW

输出 #4

.... ..S. .SS. SS.. X... .........|||||||||| .........||......|| ||||||...||......|| ||..||...||......|| ||||||.X.||||||||||

说明/提示

部分样例有其他正确答案。

「数据范围」

本题开启 Special Judge 与捆绑测试。

一个测试点内，如果对于每组数据你的箱子数是最多的，且方案合法，你才能获得该测试点的分数。

只有通过一个子任务内的所有测试点才能得到该子任务的分数。

对于所有测试数据，保证：

1≤n,m≤20001\leq n,m\leq 20001≤n,m≤2000，1≤∑nm≤4×1061\leq \sum nm\leq 4\times 10^61≤∑nm≤4×106。
1≤x≤n1\leq x\leq n1≤x≤n，1≤y≤m1\leq y\leq m1≤y≤m。
1≤k,∑k≤1061\leq k,\sum k\leq 10^61≤k,∑k≤106。
si∈{W,A,S,D}s_i\in\{\texttt{W},\texttt{A},\texttt{S},\texttt{D}\}si∈{W,A,S,D}。
小β\betaβ的移动在空旷地图下一定合法。

子任务	n,mn,mn,m	∑nm\sum nm∑nm	∑k\sum k∑k	特殊性质	分值
000	≤4\leq4≤4	≤40\leq 40≤40	≤100\leq100≤100	无	101010
111	=45=45=45	=2025=2025=2025	≤103\leq10^3≤103	A	101010
222	≤200\leq200≤200	≤4×104\leq 4\times 10^4≤4×104	≤103\leq10^3≤103	无	202020
333	≤1000\leq1000≤1000	≤2×106\leq 2\times 10^6≤2×106	≤106\leq10^6≤106	B	151515
444	≤1000\leq1000≤1000	≤2×106\leq 2\times 10^6≤2×106	≤106\leq10^6≤106	C	202020
555	≤2000\leq2000≤2000	≤4×106\leq 4\times 10^6≤4×106	≤106\leq10^6≤106	无	252525

特殊性质 A：前进和后退的总次数不超过202020次，且x=y=23x=y=23x=y=23。
特殊性质 B：si∈{W,A,D}s_i\in\{\texttt{W},\texttt{A},\texttt{D}\}si∈{W,A,D}，且只会朝两个方向前进。
特殊性质 C：可放箱子的最大数量为000或111。

尽管比赛中不会返回，我们仍将告诉你 Special Judge 会返回的对应信息，优先级递减。

Error: 1：出现规定以外的字符。
Error: 2：出生点不在正确的位置。
Error: 3：机器人无法前进。
Error: 4：机器人无法后退。
Error: 5：有箱子没有被推动过。
Error: 6：箱子数不是最多的。
Correct：测试点通过。

C++实现

#include<bits/stdc++.h>usingnamespacestd;constintN=2003,K=1e6+6;intt,n,m,sx,sy,k,g[N][N];intd[4][2]={{-1,0},{0,1},{1,0},{0,-1}};boolval[N*N],del[N*N];chars[K];intmain(){scanf("%d",&t);while(t--){scanf("%d%d%d%d%d%s",&n,&m,&sx,&sy,&k,s+1);for(inti=1,cnt=0;i<=n;i++)for(intj=1;j<=m;j++)g[i][j]=++cnt,val[g[i][j]]=del[g[i][j]]=0;intx=sx,y=sy,p=0;//x,y存机器人现在的坐标，p存方向del[g[x][y]]=1,g[x][y]=0;//删除起点上的箱子for(inti=1;i<=k;i++){if(s[i]=='A')p=(p+3)%4;//左转elseif(s[i]=='D')p=(p+1)%4;elseif(s[i]=='W'){intxx=x+d[p][0],yy=y+d[p][1];if(g[xx][yy]){intxxx=xx+d[p][0],yyy=yy+d[p][1];if(0<xxx&&xxx<=n&&0<yyy&&yyy<=m)del[g[xxx][yyy]]=1,g[xxx][yyy]=g[xx][yy],val[g[xx][yy]]=1;elsedel[g[xx][yy]]=1;g[xx][yy]=0;}x=xx,y=yy;}elseif(s[i]=='S'){intxx=x+d[(p+2)%4][0],yy=y+d[(p+2)%4][1];if(g[xx][yy])del[g[xx][yy]]=1,g[xx][yy]=0;x=xx,y=yy;//后退，有箱子删}}for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){if(i==sx&&j==sy)printf("X");//起点要特判elseprintf("%c",val[(i-1)*m+j]&&!del[(i-1)*m+j]?'S':'.');}puts("");}}return0;}