UVA101

UVA101 The Blocks Problem题目描述PDF输入格式输出格式输入输出样例 #1输入 #110 move 9 onto 1 move 8 over 1 move 7 over 1 move 6 over 1 pile 8 over 6 pile 8 over 5 move 2 over 1 move 4 over 9 quit输出 #10: 0 1: 1 9 2 4 2: 3: 3 4: 5: 5 8 7 6 6: 7: 8: 9:题目大意计算机科学很多领域会使用简单抽象模型做理论和实验研究。比如早期人工智能的规划与机器人研究STRIPS就使用积木世界模型机械臂完成积木搬运任务。本题要模拟简单积木世界遵循给定规则。不用自己寻找达到目标状态的方案而是编写程序让机械臂按照一系列指令操作积木。初始状态桌上有n块积木编号0 ~ n-1依次并排摆在桌面上每块单独占一个位置。机械臂操作积木的合法指令如下move a onto b其中 a、b 为积木编号先将堆积在积木 a 和积木 b 上方的所有积木放回各自初始位置再把积木 a 放到积木 b 之上。move a over b其中 a、b 为积木编号先将堆积在积木 a 上方的所有积木放回各自初始位置再把积木 a 放到包含积木 b 的那一堆积木的顶端。pile a onto b其中 a、b 为积木编号将由积木 a 以及堆叠在 a 上方的所有积木组成的整叠积木移动到积木 b 之上。执行堆叠操作前需要先把积木 b 上方的所有积木放回各自初始位置。堆叠在 a 上方的积木在移动时保持原有上下顺序不变。pile a over b其中 a、b 为积木编号将由积木 a 以及堆叠在 a 上方的所有积木组成的整叠积木放到包含积木 b 的那一堆积木的顶端。堆叠在 a 上方的积木在移动时保持原有上下顺序不变。quit终止积木世界的所有操作。如果一条指令满足 a 等于 b或者 a 与 b 原本就在同一堆积木中则该指令为非法指令。所有非法指令都应当被忽略不会对积木的摆放状态产生任何影响。输入第一行单独一个整数n代表积木总数0n25。之后每行一条指令直到读到quit停止。保证所有指令语法正确。输出输出积木世界的最终状态。一共输出n行对应原始位置0,1,…,n-1每行格式位置号冒号后面如果有积木先加空格接着输出这一堆积木编号空格分隔不能行尾多余空格如果该位置没有积木就只输出位置号。解题思路用一个二维列表保存每一堆积木另外开一个数组记录每一块积木当前在哪一堆用来快速查询位置避免每次遍历查找。程序先读取积木总数初始化状态每块积木一开始单独占一堆。接着循环读取每一条指令读到 quit 就停止输入。处理指令时先判断是否非法a 等于 b 或者两块积木本来就在同一堆就直接跳过这条指令。如果指令里是 onto就先把 b 上方所有积木放回各自初始位置如果是 move 操作就把 a 上方所有积木放回初始位置再单独移动 a如果是 pile 操作就把 a 以及 a 上方的一整叠积木完整移过去保持积木之间的上下顺序。移动积木时同步更新位置数组。全部指令处理完成后按堆号从小到大输出每一堆里的积木。完整代码importjava.util.*;publicclassTheBlocksProblem{privatestaticListListIntegerworld;privatestaticint[]positionOf;privatestaticintn;privatestaticListString[]readInput(Scannerscanner){nInteger.parseInt(scanner.nextLine().trim());initWorld(n);ListString[]commandsnewArrayList();while(scanner.hasNextLine()){Stringlinescanner.nextLine().trim();if(line.isEmpty())continue;String[]tokensline.split(\\s);if(tokens[0].equals(quit)){break;}commands.add(tokens);}returncommands;}privatestaticvoidinitWorld(intn){worldnewArrayList();positionOfnewint[n];for(inti0;in;i){ListIntegerpilenewArrayList();pile.add(i);world.add(pile);positionOf[i]i;}}privatestaticvoidprocessCommands(ListString[]commands){for(String[]cmd:commands){Stringactioncmd[0];intaInteger.parseInt(cmd[1]);Stringprepcmd[2];intbInteger.parseInt(cmd[3]);if(ab||positionOf[a]positionOf[b]){continue;}if(prep.equals(onto)){returnAbove(b);}if(action.equals(move)){returnAbove(a);moveBlock(a,b);}else{// pilemovePile(a,b);}}}privatestaticvoidreturnAbove(intblock){intpospositionOf[block];ListIntegerpileworld.get(pos);intidxpile.indexOf(block);for(intipile.size()-1;iidx;i--){inttopBlockpile.remove(i);returnToInitial(topBlock);}}privatestaticvoidreturnToInitial(intblock){intinitPosblock;positionOf[block]initPos;world.get(initPos).add(block);}privatestaticvoidmoveBlock(inta,intb){intposApositionOf[a];intposBpositionOf[b];world.get(posA).remove(Integer.valueOf(a));world.get(posB).add(a);positionOf[a]posB;}privatestaticvoidmovePile(inta,intb){intposApositionOf[a];intposBpositionOf[b];ListIntegerpileAworld.get(posA);intidxpileA.indexOf(a);ListIntegermovingBlocksnewArrayList(pileA.subList(idx,pileA.size()));pileA.subList(idx,pileA.size()).clear();for(intblock:movingBlocks){world.get(posB).add(block);positionOf[block]posB;}}privatestaticvoidprintResult(){StringBuildersbnewStringBuilder();for(inti0;in;i){sb.append(i).append(:);ListIntegerpileworld.get(i);for(intblock:pile){sb.append( ).append(block);}sb.append(\n);}System.out.print(sb);}publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);ListString[]commandsreadInput(sc);processCommands(commands);printResult();sc.close();}}测评结果