当前位置：首页 > news >正文

UVa 411 Centipede Collisions

news 2026/6/7 17:44:59

题目描述

题目模拟一个30×3030 \times 3030×30的网格上多条蜈蚣的运动。每条蜈蚣由若干长度为111厘米的节段组成，所有节段同时沿着同一方向移动（上、下、左、右）。蜈蚣按照编号顺序循环移动（先移动蜈蚣000，然后蜈蚣111，依此类推）。当两个或更多蜈蚣的节段在同一时刻占据同一个网格单元时，发生碰撞。碰撞发生后，所有处于碰撞位置的节段停止并永久占据该位置（标记为X），该蜈蚣上位于碰撞节段之后（远离头部方向）的节段会脱离并继续移动，直到再次发生碰撞、遇到已有的碰撞位置或移出网格边界。当所有节段都已进入碰撞位置或移出网格后，模拟结束。

输入格式

输入包含多组模拟数据。每组数据格式如下：

第一行一个整数NNN（1≤N≤101 \le N \le 101≤N≤10），表示蜈蚣的数量。蜈蚣按输入顺序编号为000到N−1N-1N−1。
接下来NNN行，每行描述一条蜈蚣：一个方向字符（U表示向上、D表示向下、L表示向左、R表示向右），然后三个整数：长度LLL（1≤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到292929），yyy坐标为垂直方向（000到292929）。输出时行号从292929到000000，即网格的顶部对应y=29y = 29y=29，底部对应y=0y = 0y=0。存储时可以使用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×2=6030 \times 2 = 6030×2=60步（从一端到另一端），总复杂度O(N×L×steps)O(N \times L \times \text{steps})O(N×L×steps)，N≤10N \le 10N≤10，L≤30L \le 30L≤30，完全可接受。

代码实现

// Centipede Collisions// UVa ID: 411// Verdict: Accepted// Submission Date: 2017-02-23// UVa Run Time: 0.000s//// 版权所有（C）2017，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;// L, U, R, Dmap<char,int>directions={{'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(cin>>n){memset(grid,'.',sizeof(grid));chardirection;intlength,x,y;for(inti=0;i<n;i++){cin>>direction>>length>>x>>y;centipedes[i].x=x;centipedes[i].y=y;centipedes[i].length=length;centipedes[i].offsetx=offset[directions[direction]][0];centipedes[i].offsety=offset[directions[direction]][1];for(intj=0;j<length;j++){grid[29-y][x]=i+'0';x-=offset[directions[direction]][0];y-=offset[directions[direction]][1];centipedes[i].segments[j]=1;}}while(true){boolupdated=false;for(inti=0;i<n;i++){intxx=centipedes[i].x,yy=centipedes[i].y;for(intj=0;j<centipedes[i].length;j++){if(centipedes[i].segments[j]>0){if(xx>=0&&xx<=29&&yy>=0&&yy<=29){if(grid[29-yy][xx]=='X'){centipedes[i].segments[j]=0;updated=true;}}}xx-=centipedes[i].offsetx;yy-=centipedes[i].offsety;}xx=centipedes[i].x,yy=centipedes[i].y;for(intj=0;j<centipedes[i].length;j++){if(xx>=0&&xx<=29&&yy>=0&&yy<=29){if(grid[29-yy][xx]==(i+'0'))grid[29-yy][xx]='.';}xx-=centipedes[i].offsetx;yy-=centipedes[i].offsety;}centipedes[i].x+=centipedes[i].offsetx;centipedes[i].y+=centipedes[i].offsety;xx=centipedes[i].x,yy=centipedes[i].y;for(intj=0;j<centipedes[i].length;j++){if(centipedes[i].segments[j]>0){if(xx>=0&&xx<=29&&yy>=0&&yy<=29){if(grid[29-yy][xx]!='.'){grid[29-yy][xx]='X';centipedes[i].segments[j]=0;}else{grid[29-yy][xx]=i+'0';}}else{centipedes[i].segments[j]=0;}updated=true;}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(inti=0;i<30;i++){intlabel=29-i;cout<<setw(2)<<setfill('0')<<label;for(intj=0;j<30;j++)cout<<' '<<grid[i][j];cout<<'\n';}cout<<'\n';}return0;}