UVa 411 Centipede Collisions

题目描述题目模拟一个30×3030 \times 3030×30的网格上多条蜈蚣的运动。每条蜈蚣由若干长度为111厘米的节段组成所有节段同时沿着同一方向移动上、下、左、右。蜈蚣按照编号顺序循环移动先移动蜈蚣000然后蜈蚣111依此类推。当两个或更多蜈蚣的节段在同一时刻占据同一个网格单元时发生碰撞。碰撞发生后所有处于碰撞位置的节段停止并永久占据该位置标记为X该蜈蚣上位于碰撞节段之后远离头部方向的节段会脱离并继续移动直到再次发生碰撞、遇到已有的碰撞位置或移出网格边界。当所有节段都已进入碰撞位置或移出网格后模拟结束。输入格式输入包含多组模拟数据。每组数据格式如下第一行一个整数NNN1≤N≤101 \le N \le 101≤N≤10表示蜈蚣的数量。蜈蚣按输入顺序编号为000到N−1N-1N−1。接下来NNN行每行描述一条蜈蚣一个方向字符U表示向上、D表示向下、L表示向左、R表示向右然后三个整数长度LLL1≤L≤301 \le L \le 301≤L≤30、头部节段的xxx坐标和yyy坐标0≤x,y≤290 \le x, y \le 290≤x,y≤29。蜈蚣的其余L−1L-1L−1个节段从头部开始向相反方向依次排列。初始配置保证所有节段均在网格内且无碰撞。输出格式对于每组模拟数据首先输出两行固定的表头从第444列开始第一行0000000000111111111222222222第二行012345678901234567890123456789接下来输出303030行每行表示网格的一行。行号从292929到000000每行前两列为行号两位数字带前导零然后从第444列开始每隔一列输出一个网格单元的内容共303030个单元格每个单元格占222个字符位置但实际内容只输出一个字符后跟一个空格。网格单元可以是.表示空单元格X表示包含两个或更多蜈蚣节段的碰撞位置每组输出后跟一个空行。样例输入10 R 9 11 23 U 8 11 17 U 5 15 15 U 5 15 8 D 9 23 13 U 6 23 6 R 9 8 9 L 13 17 0 U 12 13 11 L 5 20 9输出格式参考题目原文0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 29 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...题目分析本题的核心是模拟多蜈蚣在网格上的运动、碰撞及节段脱离过程。由于蜈蚣数量最多101010条每条长度最多303030网格大小为30×3030 \times 3030×30可以直接使用逐轮模拟的方法。坐标系统题目中xxx坐标为水平方向000到292929yyy坐标为垂直方向000到292929。输出时行号从292929到000000即网格的顶部对应y29y 29y29底部对应y0y 0y0。存储时可以使用grid[y][x]\textit{grid}[y][x]grid[y][x]的方式其中yyy为垂直坐标。蜈蚣表示每条蜈蚣需要记录头部节段的当前坐标(x,y)(x, y)(x,y)长度LLL移动方向偏移量Δx,Δy\Delta x, \Delta yΔx,Δy每个节段的状态是否存在/是否已碰撞由于蜈蚣在碰撞后位于碰撞节段之后的节段会脱离并继续移动这意味着一条蜈蚣可能分裂成多个独立移动的部分。但题目描述中“所有剩余节段从碰撞节段脱离后继续移动”且脱离后的节段之间保持连接关系。更简单的处理方式是将每条蜈蚣视为一个队列每次移动时从头部加入新位置尾部移除旧位置。碰撞发生时从碰撞节段开始往后的所有节段被“切断”这些节段不再属于原蜈蚣而作为一个新的独立移动单元继续运动。然而参考代码的实现采用了另一种方法每条蜈蚣的节段按从头部到尾部顺序存储每个节段有一个标志表示是否仍存在。在每轮移动中先清除当前蜈蚣在网格上的痕迹然后头部向前移动一格接着重新绘制从头部开始的所有存在节段。如果某节段在移动后进入了已有X的位置或与其他蜈蚣节段重叠则将该节段标记为消失并在该位置放置X。模拟流程初始化根据输入放置所有蜈蚣的节段到网格上每个节段用其所属蜈蚣的编号字符0到9表示。循环模拟重复以下过程直到没有任何节段可以移动按编号顺序处理每条蜈蚣a. 对于当前蜈蚣的所有存在节段检查它们所在位置是否为X。如果是则将这些节段标记为消失因为它们已进入碰撞位置。b. 清除当前蜈蚣在网格上的所有痕迹将对应位置设为.但注意这些位置可能也是其他蜈蚣的节段实际上在清除前这些位置只属于当前蜈蚣因为不同蜈蚣的节段不能在同一位置共存——若共存则已标记为X。c. 头部向前移动一格。d. 从新的头部开始依次处理每个存在节段的新位置如果新位置超出网格边界该节段标记为消失。如果新位置已经有X已有碰撞或其他蜈蚣的节段非当前蜈蚣且非.则将当前位置设为X并将该节段标记为消失。否则将当前位置设为当前蜈蚣的编号。e. 如果没有任何节段被移动即所有节段都已消失则模拟结束。输出按照指定格式输出最终的网格状态。碰撞处理细节当多个节段在同一时刻进入同一个空单元格时它们会发生碰撞。参考代码的处理方式是在移动阶段如果某个节段的新位置已有其他蜈蚣的节段即非.且非X则将那个位置标记为X同时将当前节段标记为消失。但这样只能处理两个节段同时到达的情况如果两个节段同时进入一个空单元格后处理的蜈蚣会看到前一个蜈蚣已经放置的编号从而触发碰撞。由于蜈蚣按顺序移动后移动的蜈蚣会检测到前一个已经放置的节段从而正确标记碰撞。已存在的X位置被视为障碍任何进入该位置的节段都会消失加入碰撞。复杂度分析每条蜈蚣每次移动最多遍历其长度个节段每次移动后至少有一个节段消失或所有节段都无法再移动。每个节段最多移动30×26030 \times 2 6030×260步从一端到另一端总复杂度O(N×L×steps)O(N \times L \times \text{steps})O(N×L×steps)N≤10N \le 10N≤10L≤30L \le 30L≤30完全可接受。代码实现// Centipede Collisions// UVa ID: 411// Verdict: Accepted// Submission Date: 2017-02-23// UVa Run Time: 0.000s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// L, U, R, Dmapchar,intdirections{{L,0},{U,1},{R,2},{D,3}};intoffset[4][2]{{-1,0},{0,1},{1,0},{0,-1}};structcentipede{intx,y,length,offsetx,offsety,segments[40];};centipede centipedes[20];chargrid[40][40];intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intn;while(cinn){memset(grid,.,sizeof(grid));chardirection;intlength,x,y;for(inti0;in;i){cindirectionlengthxy;centipedes[i].xx;centipedes[i].yy;centipedes[i].lengthlength;centipedes[i].offsetxoffset[directions[direction]][0];centipedes[i].offsetyoffset[directions[direction]][1];for(intj0;jlength;j){grid[29-y][x]i0;x-offset[directions[direction]][0];y-offset[directions[direction]][1];centipedes[i].segments[j]1;}}while(true){boolupdatedfalse;for(inti0;in;i){intxxcentipedes[i].x,yycentipedes[i].y;for(intj0;jcentipedes[i].length;j){if(centipedes[i].segments[j]0){if(xx0xx29yy0yy29){if(grid[29-yy][xx]X){centipedes[i].segments[j]0;updatedtrue;}}}xx-centipedes[i].offsetx;yy-centipedes[i].offsety;}xxcentipedes[i].x,yycentipedes[i].y;for(intj0;jcentipedes[i].length;j){if(xx0xx29yy0yy29){if(grid[29-yy][xx](i0))grid[29-yy][xx].;}xx-centipedes[i].offsetx;yy-centipedes[i].offsety;}centipedes[i].xcentipedes[i].offsetx;centipedes[i].ycentipedes[i].offsety;xxcentipedes[i].x,yycentipedes[i].y;for(intj0;jcentipedes[i].length;j){if(centipedes[i].segments[j]0){if(xx0xx29yy0yy29){if(grid[29-yy][xx]!.){grid[29-yy][xx]X;centipedes[i].segments[j]0;}else{grid[29-yy][xx]i0;}}else{centipedes[i].segments[j]0;}updatedtrue;}xx-centipedes[i].offsetx;yy-centipedes[i].offsety;}}if(!updated)break;}cout 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2\n;cout 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9\n;for(inti0;i30;i){intlabel29-i;coutsetw(2)setfill(0)label;for(intj0;j30;j)cout grid[i][j];cout\n;}cout\n;}return0;}