打卡信奥刷题（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输入 #11 3 4 2 2 17 DWSAWDWSSDWAWDWAW输出 #1..S. SXS. ..S.输入输出样例 #2输入 #21 3 4 3 4 9 WSAWWDWDW输出 #2|.|. |SSS ..SX输入输出样例 #3输入 #31 3 4 2 1 8 DWASDWAW输出 #3||.| XS.| |.S.输入输出样例 #4输入 #42 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≤20001≤∑nm≤4×1061\leq \sum nm\leq 4\times 10^61≤∑nm≤4×106。1≤x≤n1\leq x\leq n1≤x≤n1≤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无101010111454545202520252025≤103\leq10^3≤103A101010222≤200\leq200≤200≤4×104\leq 4\times 10^4≤4×104≤103\leq10^3≤103无202020333≤1000\leq1000≤1000≤2×106\leq 2\times 10^6≤2×106≤106\leq10^6≤106B151515444≤1000\leq1000≤1000≤2×106\leq 2\times 10^6≤2×106≤106\leq10^6≤106C202020555≤2000\leq2000≤2000≤4×106\leq 4\times 10^6≤4×106≤106\leq10^6≤106无252525特殊性质 A前进和后退的总次数不超过202020次且xy23xy23xy23。特殊性质 Bsi∈{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实现#includebits/stdc.husingnamespacestd;constintN2003,K1e66;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,s1);for(inti1,cnt0;in;i)for(intj1;jm;j)g[i][j]cnt,val[g[i][j]]del[g[i][j]]0;intxsx,ysy,p0;//x,y存机器人现在的坐标p存方向del[g[x][y]]1,g[x][y]0;//删除起点上的箱子for(inti1;ik;i){if(s[i]A)p(p3)%4;//左转elseif(s[i]D)p(p1)%4;elseif(s[i]W){intxxxd[p][0],yyyd[p][1];if(g[xx][yy]){intxxxxxd[p][0],yyyyyd[p][1];if(0xxxxxxn0yyyyyym)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;}xxx,yyy;}elseif(s[i]S){intxxxd[(p2)%4][0],yyyd[(p2)%4][1];if(g[xx][yy])del[g[xx][yy]]1,g[xx][yy]0;xxx,yyy;//后退有箱子删}}for(inti1;in;i){for(intj1;jm;j){if(isxjsy)printf(X);//起点要特判elseprintf(%c,val[(i-1)*mj]!del[(i-1)*mj]?S:.);}puts();}}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容