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

rogeliu

565人浏览 · 2026-10-14 08:45:20

rogeliu · 2026-10-14 08:45:20 发布

P11864 「o.OI R1」α+β Problem

题目背景

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

题目描述

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

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

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

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

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

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

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

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

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

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

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

输入格式

本题有多组数据。

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

对于每组数据：

第一行两个整数 $n, m$ 。
第二行三个整数 $x, y, k$ 。
第三行一个长度为 $k$ 的字符串 $s$ 。

输入的数据含义如下：

$n$ 和 $m$ 代表需要构造的地图的大小为 $n$ 行 $m$ 列。
$x$ 和 $y$ 代表机器人的初始位置在从上往下第 $x$ 行从左往右第 $y$ 列。
$k$ 代表移动路径的长度， $s$ 代表移动路径。

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

输出格式

对于每组数据，你需要给出一个 $n×mn\times 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 2000$ ， $1≤∑nm≤4×1061\leq \sum nm\leq 4\times 10^6$ 。
$1≤x≤n1\leq x\leq n$ ， $1≤y≤m1\leq y\leq m$ 。
$1≤k,∑k≤1061\leq k,\sum k\leq 10^6$ 。
$si∈{W,A,S,D}s_i\in\{\texttt{W},\texttt{A},\texttt{S},\texttt{D}\}$ 。
小 $β\beta$ 的移动在空旷地图下一定合法。

子任务	$n, m$	$∑nm\sum nm$	$∑k\sum k$	特殊性质	分值
$0$	$≤4\leq4$	$≤40\leq 40$	$≤100\leq100$	无	$10$
$1$	$= 45$	$= 2025$	$≤103\leq10^3$	A	$10$
$2$	$≤200\leq200$	$≤4×104\leq 4\times 10^4$	$≤103\leq10^3$	无	$20$
$3$	$≤1000\leq1000$	$≤2×106\leq 2\times 10^6$	$≤106\leq10^6$	B	$15$
$4$	$≤1000\leq1000$	$≤2×106\leq 2\times 10^6$	$≤106\leq10^6$	C	$20$
$5$	$≤2000\leq2000$	$≤4×106\leq 4\times 10^6$	$≤106\leq10^6$	无	$25$

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

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

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

C++实现

#include <bits/stdc++.h>
using namespace std;
const int N=2003,K=1e6+6;
int t,n,m,sx,sy,k,g[N][N];
int d[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
bool val[N*N],del[N*N];
char s[K];
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d%d%d%s",&n,&m,&sx,&sy,&k,s+1);
        for(int i=1,cnt=0;i<=n;i++)
            for(int j=1;j<=m;j++)
                g[i][j]=++cnt,val[g[i][j]]=del[g[i][j]]=0;
        int x=sx,y=sy,p=0;//x,y存机器人现在的坐标，p存方向
        del[g[x][y]]=1,g[x][y]=0;//删除起点上的箱子
        for(int i=1;i<=k;i++){
            if(s[i]=='A')
                p=(p+3)%4;//左转
            else if(s[i]=='D')
                p=(p+1)%4;
            else if(s[i]=='W'){
                int xx=x+d[p][0],yy=y+d[p][1];
                if(g[xx][yy]){
                    int xxx=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;
                    else
                        del[g[xx][yy]]=1;
                    g[xx][yy]=0;
                }
                x=xx,y=yy;
            }else if(s[i]=='S'){
                int xx=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(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(i==sx && j==sy)
                    printf("X");//起点要特判
                else
                    printf("%c",val[(i-1)*m+j] && !del[(i-1)*m+j]? 'S':'.');
            }
            puts(""); 
        }
    }
    return 0;
}