#题目描述
###Background
Many areas of Computer Science use simple, abstract domains for both analytical and empirical studies. For example, an early AI study of planning and robotics (STRIPS) used a block world in which a robot arm performed tasks involving the manipulation of blocks.
In this problem you will model a simple block world under certain rules and constraints. Rather than determine how to achieve a specified state, you will ``program'' a robotic arm to respond to a limited set of commands.
###The Problem
The problem is to parse a series of commands that instruct a robot arm in how to manipulate blocks that lie on a flat table. Initially there are n blocks on the table (numbered from 0 to n-1) with block bi adjacent to block bi+1 for all 0 <= i < n-1 as shown in the diagram below:
Figure: Initial Blocks World
The valid commands for the robot arm that manipulates blocks are:
move a onto b
where a and b are block numbers, puts block a onto block b after returning any blocks that are stacked on top of blocks a and b to their initial positions.
move a over b
where a and b are block numbers, puts block a onto the top of the stack containing block b, after returning any blocks that are stacked on top of block a to their initial positions.
pile a onto b
where a and b are block numbers, moves the pile of blocks consisting of block a, and any blocks that are stacked above block a, onto block b. All blocks on top of block b are moved to their initial positions prior to the pile taking place. The blocks stacked above block a retain their order when moved.
pile a over b
where a and b are block numbers, puts the pile of blocks consisting of block a, and any blocks that are stacked above block a, onto the top of the stack containing block b. The blocks stacked above block a retain their original order when moved.
quit
terminates manipulations in the block world.
Any command in which a = b or in which a and b are in the same stack of blocks is an illegal command. All illegal commands should be ignored and should have no affect on the configuration of blocks.
###The Input
The input begins with an integer n on a line by itself representing the number of blocks in the block world. You may assume that 0 < n < 25. The number of blocks is followed by a sequence of block commands, one command per line. Your program should process all commands until the quit command is encountered.
You may assume that all commands will be of the form specified above. There will be no syntactically incorrect commands.
###The Output
The output should consist of the final state of the blocks world. Each original block position numbered i ( 0 < i < n where n is the number of blocks) should appear followed immediately by a colon. If there is at least a block on it, the colon must be followed by one space, followed by a list of blocks that appear stacked in that position with each block number separated from other block numbers by a space. Don't put any trailing spaces on a line.
There should be one line of output for each block position (i.e., n lines of output where n is the integer on the first line of input).
###Sample Input
10move 9 onto 1move 8 over 1move 7 over 1move 6 over 1pile 8 over 6pile 8 over 5move 2 over 1move 4 over 9quit
###Sample Output
0: 0 1: 1 9 2 4 2: 3: 3 4: 5: 5 8 7 6 6: 7: 8: 9:
#题目简述
这个题目的整体也就是模拟机器手臂搬东西,在整个过程中,机器手臂只能执行四种命令。如果是非法的命令的话你得忽略这些非法的命令,下面我将详细道来。
###move a onto b
将a移动到b上,在a和b上面的都挪回到初始位置。
###move a over b
将a移动到b那一堆,在a上面的都挪回到初始位置。
###pile a onto b
将a那一堆移动到b上,在b上面的都挪回到初始位置。
###pile a over b
将a那一堆移动到b那一堆
##注意的地方
其实,就是要区分 move 和 pile的区别,move 一次只能挪一个,而pile 一次挪一堆。还有 onto 和over的区别,onto 是直接在b上, 而over 是在b所在的那一堆上。
最后就是,非法情况了,一定不要把这个给遗忘了。如果a和b相同,或者a和b在同一堆都是非法的情况。
#附上代码
import java.util.ArrayList;import java.util.List;import java.util.Scanner;import java.util.Stack;public class Main { private static List> blocks; public static void main(String[] args) { Scanner cin = new Scanner(System.in); int n = cin.nextInt(); blocks = new ArrayList<>(); for (int i = 0; i <= n; i++) { Stack tmp = new Stack<>(); if (i < n) { tmp.push(i); } blocks.add(tmp); } //处理整个输入和处理逻辑 while (true) { String cmd = cin.next(); if (cmd.equals("quit")) { break; } else if (cmd.equals("move")) { int a = cin.nextInt(); String subCmd = cin.next(); int b = cin.nextInt(); int whereA = findBlock(a); int whereB = findBlock(b); if (!isIllegalCmd(whereA, whereB, a, b)) { continue; } if (subCmd.equals("onto")) { initPosition(a, whereA); initPosition(b, whereB); moveAToB(whereA, whereB); } else if (subCmd.equals("over")) { initPosition(a, whereA); moveAToB(whereA, whereB); } } else if (cmd.equals("pile")) { int a = cin.nextInt(); String subCmd = cin.next(); int b = cin.nextInt(); int whereA = findBlock(a); int whereB = findBlock(b); if (!isIllegalCmd(whereA, whereB, a, b)) { continue; } if (subCmd.equals("onto")) { initPosition(b, whereB); pileAToB(whereA, whereB, a); } else if (subCmd.equals("over")) { pileAToB(whereA, whereB, a); } } } for (int i = 0; i < blocks.size() - 1; i++) { System.out.print(i + ":"); Stack tmp = new Stack<>(); Stack origin = blocks.get(i); while (!origin.empty()) { int p = origin.pop(); tmp.push(p); } while (!tmp.empty()) { System.out.print(" " + tmp.pop()); } System.out.println(); } } //将p 所对应的位置i上面的所有block都挪到初始位置 private static void initPosition(int p, int i) { Stack tmp = blocks.get(i); while (true) { int b = tmp.peek(); if (b == p) { break; } tmp.pop(); blocks.get(b).push(b); } } //找到p所对应的block所在的堆 private static int findBlock(int p) { int i; boolean flag = false; for (i = 0; i < blocks.size() - 1; i++) { Stack tmp = blocks.get(i); for (Integer b : tmp) { if (b == p) { flag = true; break; } } if (flag) { break; } } return i; } //将堆 whereA 上的第一个,移动到 堆 whereB堆上 private static void moveAToB(int whereA, int whereB) { int a = blocks.get(whereA).pop(); blocks.get(whereB).push(a); } //将堆 whereA 的p及以上的block 都挪到 堆whereB上 private static void pileAToB(int whereA, int whereB, int p) { Stack tmp = blocks.get(blocks.size() - 1); tmp.clear(); Stack stackA = blocks.get(whereA); while (true) { int a = stackA.pop(); tmp.push(a); if (a == p) { break; } } Stack stackB = blocks.get(whereB); while (!tmp.empty()) { int b = tmp.pop(); stackB.push(b); } } //判断命令是否合法 private static boolean isIllegalCmd(int whereA, int whereB, int a, int b) { return a != b && whereA != whereB; }}
#附上一组 测试数据
24move 2 over 8pile 11 onto 18pile 13 onto 15pile 22 over 15move 17 over 11move 12 over 7pile 4 onto 17move 19 over 22pile 11 over 18move 21 onto 4pile 23 onto 9pile 13 over 15move 6 over 16move 21 over 12move 9 onto 5move 21 onto 11move 14 onto 7pile 18 over 9pile 1 over 12move 3 over 13pile 7 onto 4pile 14 over 1move 19 over 1pile 9 over 20pile 22 onto 17pile 2 over 17move 11 over 1move 19 onto 15move 6 onto 15move 6 onto 22pile 17 onto 9move 11 onto 22pile 19 onto 6move 7 onto 3pile 20 onto 3move 15 onto 8move 18 onto 21move 21 onto 21pile 14 over 4pile 18 over 16move 18 over 12pile 9 onto 2pile 12 onto 7move 4 onto 8pile 18 onto 10move 3 onto 18move 18 over 1pile 6 over 13pile 3 over 4pile 17 onto 19move 22 onto 15move 5 over 19pile 19 over 4move 22 over 17move 23 over 5pile 15 over 21move 5 over 11move 3 over 11pile 19 over 20pile 8 onto 22pile 0 over 12pile 4 onto 2move 23 onto 18pile 8 over 6move 15 over 13pile 9 over 1pile 1 over 15pile 20 onto 11pile 12 over 4move 9 over 23move 17 over 11pile 13 onto 6move 19 onto 21move 14 over 21pile 5 onto 15pile 9 over 2move 22 over 20pile 5 onto 21pile 22 over 17move 22 onto 0move 23 over 15pile 19 onto 9pile 19 onto 7pile 23 onto 4pile 10 onto 0move 18 over 4move 4 onto 21move 1 over 11pile 2 over 19pile 17 onto 9pile 22 onto 3pile 11 over 8move 3 over 3pile 15 over 8move 18 over 17move 13 over 0pile 3 onto 13pile 2 onto 11move 7 over 0move 14 over 11move 3 over 10pile 6 over 0move 3 over 14pile 22 onto 0pile 10 onto 9move 15 over 14move 18 onto 10move 13 over 2pile 18 onto 17pile 7 over 4pile 1 onto 16move 10 over 11move 6 onto 23move 21 onto 15pile 15 over 2pile 12 over 5pile 1 over 0move 3 over 16pile 22 over 21move 6 over 1pile 12 onto 7pile 12 onto 14move 10 onto 12move 5 over 14pile 12 onto 20pile 20 over 13pile 6 onto 6move 20 over 17move 23 over 23pile 7 onto 14move 21 over 7pile 18 onto 0pile 18 onto 7move 17 onto 20pile 22 onto 19pile 6 onto 23move 17 over 7move 21 onto 7pile 12 onto 6move 23 over 4pile 16 over 6pile 21 onto 6move 18 over 13move 12 over 20pile 11 onto 2move 7 onto 1pile 11 over 2move 13 onto 18pile 5 onto 19pile 5 onto 16pile 18 over 14pile 22 over 5pile 18 over 17move 11 onto 1move 14 over 18move 12 onto 4pile 10 onto 13move 21 onto 19move 3 onto 12move 0 over 23pile 17 over 10pile 15 onto 13move 21 over 5move 14 onto 8pile 5 onto 4pile 10 onto 18move 13 over 17pile 15 onto 21pile 20 onto 11pile 7 over 11pile 20 onto 4pile 9 onto 22pile 23 over 8pile 0 onto 13pile 9 over 23move 7 over 22move 4 over 7pile 15 over 23move 12 over 9pile 23 over 16move 4 over 22move 15 onto 21pile 19 over 21move 3 onto 1pile 3 onto 7pile 9 over 22pile 16 over 9move 2 onto 23pile 6 onto 14move 9 over 16move 9 over 0move 13 over 6move 22 onto 1pile 7 onto 12move 0 onto 6move 0 over 15move 19 onto 13move 20 onto 6move 12 onto 7pile 4 onto 21pile 22 onto 17move 6 onto 9move 20 over 7pile 8 onto 12move 9 onto 4pile 21 over 7move 7 over 13pile 10 over 10pile 14 onto 15move 17 over 16pile 0 onto 3move 18 over 11move 7 over 12move 13 onto 10move 12 over 15pile 8 over 8pile 2 onto 7move 1 onto 19pile 14 over 10move 18 over 13move 2 onto 6move 2 over 7pile 18 onto 16move 1 onto 9pile 4 over 16move 3 onto 8move 22 onto 0move 7 onto 12pile 14 over 18move 10 onto 21pile 12 onto 4pile 2 over 16pile 15 onto 4move 15 over 1move 12 over 16pile 21 over 9move 15 over 12move 15 over 20move 11 onto 19pile 0 over 1move 14 onto 13move 4 over 7pile 12 onto 4pile 20 over 19pile 1 over 15move 19 onto 8pile 18 onto 2move 6 onto 14move 23 onto 14pile 8 onto 2move 10 over 18pile 21 over 23move 20 over 2pile 23 over 11pile 0 over 0move 9 over 17pile 19 over 14move 8 over 1pile 4 onto 8move 16 onto 6move 17 over 17pile 6 over 2pile 12 onto 8move 12 onto 23pile 21 onto 8pile 1 onto 16pile 10 onto 5move 4 over 5pile 12 over 23pile 16 over 19move 1 over 10move 8 over 14move 18 onto 13pile 5 over 10pile 13 onto 13move 4 onto 21move 20 onto 5pile 19 over 19move 8 over 23move 19 onto 12move 11 over 17move 8 over 11move 23 onto 22pile 4 over 19move 12 onto 18move 8 over 5move 15 onto 9pile 19 onto 12pile 12 over 12pile 5 over 14move 7 onto 4move 17 over 3move 18 onto 22move 3 over 11move 7 onto 0pile 23 over 3pile 7 over 11pile 21 over 17pile 19 over 5pile 8 onto 23move 6 over 17pile 6 onto 9pile 20 onto 19move 19 onto 21move 2 over 1pile 18 onto 15pile 2 onto 16pile 0 over 3move 17 onto 15pile 23 onto 12move 13 over 14move 4 onto 3move 13 onto 21pile 21 over 20move 8 over 1pile 20 over 6move 11 onto 21pile 0 onto 3pile 17 over 21pile 19 onto 13pile 7 over 0move 3 over 4move 7 over 20pile 1 over 12pile 8 onto 9pile 21 onto 17pile 10 onto 14move 14 over 23pile 1 onto 1pile 15 over 14move 4 onto 2move 9 onto 22move 6 onto 11move 19 onto 3pile 23 onto 18pile 18 onto 12pile 20 over 13pile 18 over 23pile 20 over 13pile 17 onto 5pile 22 onto 23pile 22 over 3pile 16 over 22pile 2 onto 12move 7 onto 3pile 7 onto 10pile 0 onto 9move 13 onto 3pile 6 over 15move 0 onto 10pile 16 over 4pile 15 onto 10pile 17 over 5move 2 onto 4move 20 onto 16move 22 over 3pile 12 over 1pile 0 onto 4pile 0 over 22pile 20 over 19move 19 onto 18move 8 over 9pile 11 onto 12pile 7 over 7move 21 onto 9move 16 onto 15move 12 onto 18pile 10 onto 2move 16 over 4pile 20 over 12pile 11 over 13pile 9 onto 15move 18 over 15move 19 over 14pile 7 over 13move 13 onto 0move 11 onto 1move 13 onto 18move 21 onto 14move 15 onto 22pile 7 onto 23pile 6 onto 18pile 21 onto 14pile 8 over 21move 0 onto 17move 17 over 23pile 10 onto 4move 18 over 15pile 0 over 14pile 2 over 3move 12 over 7move 1 onto 15pile 3 onto 5pile 2 over 19pile 21 onto 20move 17 over 8move 11 over 7pile 8 onto 3pile 23 onto 18move 9 over 18move 4 onto 3move 23 onto 7pile 17 over 21move 5 onto 12move 9 over 4move 23 over 6pile 13 onto 13move 5 over 11pile 0 onto 23pile 2 over 0pile 9 onto 4pile 17 over 0pile 10 over 11move 12 onto 14move 20 onto 23pile 7 over 13pile 8 onto 4move 18 over 2pile 16 over 19move 14 onto 1pile 7 over 15move 23 over 7move 19 onto 17move 3 over 19pile 10 over 18move 4 over 5pile 0 onto 7pile 13 onto 21move 9 over 15pile 11 onto 0move 16 over 17pile 4 over 20pile 5 over 17pile 8 onto 9pile 19 over 5move 22 over 20pile 10 onto 0pile 21 over 17pile 14 over 12pile 3 over 23move 1 over 7pile 14 over 22pile 7 over 5move 11 onto 23move 3 over 17pile 17 over 10move 16 onto 14pile 10 onto 11move 5 over 15move 6 onto 16move 6 onto 8pile 16 onto 15move 9 onto 19move 6 onto 11move 10 over 22pile 11 onto 20pile 2 onto 8move 18 onto 11pile 17 onto 21move 15 over 21move 0 over 20move 5 over 2move 15 over 0move 9 over 11move 10 onto 20move 20 over 1pile 11 over 0pile 2 over 3pile 8 over 0pile 10 onto 1move 1 onto 14pile 9 over 16pile 1 over 9pile 13 onto 21move 15 onto 9pile 6 over 0pile 3 over 0move 8 onto 14move 19 over 19pile 7 onto 2move 22 over 17pile 15 over 20pile 2 onto 8move 13 over 13pile 8 over 14move 19 over 5move 20 onto 9pile 18 onto 13move 17 onto 4move 7 over 18pile 13 over 13pile 6 onto 21pile 14 over 20pile 8 over 19move 20 over 4move 14 onto 14pile 10 over 1pile 18 onto 13move 20 onto 1move 6 over 19pile 20 onto 6pile 10 onto 9pile 23 onto 7pile 5 over 20pile 13 onto 16pile 15 over 15move 18 onto 11pile 19 onto 1move 13 onto 1move 0 over 22move 4 over 6move 14 over 1move 11 onto 22pile 15 over 17pile 8 over 9move 22 over 3pile 6 over 19move 3 onto 0pile 5 onto 21pile 17 over 19pile 4 over 3move 19 over 11pile 8 over 8pile 13 onto 23move 22 onto 5move 3 over 8move 3 over 7pile 0 over 7pile 8 over 2move 11 over 1pile 23 over 6move 1 onto 1move 17 over 10pile 0 onto 0pile 12 over 6move 1 over 3move 23 onto 18pile 7 onto 14move 4 onto 7move 19 over 19pile 1 onto 3move 11 over 10move 7 onto 9pile 23 onto 14pile 5 onto 19pile 8 onto 10move 5 over 21pile 0 over 17move 0 over 14move 17 onto 6pile 8 over 14pile 14 over 9pile 16 onto 6pile 13 onto 10move 2 onto 20pile 12 over 4move 4 onto 17move 12 onto 4pile 20 onto 22pile 18 over 11move 7 over 9move 18 onto 21pile 13 onto 16move 19 over 11pile 8 onto 10move 15 onto 12pile 23 over 17pile 6 onto 5move 23 over 10move 9 over 2move 6 over 0pile 5 over 21pile 14 onto 10move 13 over 19pile 16 over 20pile 18 over 4pile 0 over 13move 13 onto 9move 13 over 23pile 12 over 22pile 7 over 10move 11 onto 15pile 9 onto 21pile 18 over 0pile 17 onto 18move 3 onto 1move 19 onto 13move 9 onto 19move 7 onto 5pile 20 over 0pile 4 over 13pile 0 over 3pile 18 over 19move 22 over 4move 18 onto 14pile 20 over 23pile 9 onto 0pile 23 onto 4pile 6 onto 13pile 19 over 4move 20 onto 3move 1 onto 11pile 14 onto 15pile 16 over 1pile 3 onto 16move 15 over 9pile 17 onto 4move 8 over 7move 19 over 1pile 17 over 1pile 5 over 19pile 23 onto 18move 9 over 3pile 13 over 2pile 20 over 21pile 14 over 8move 4 over 14pile 7 over 15pile 21 onto 10move 3 onto 8move 23 over 8pile 16 over 0pile 21 onto 3pile 2 onto 18move 20 over 12pile 11 onto 18move 18 over 9move 7 onto 11pile 20 over 21move 21 over 17pile 23 over 17pile 3 over 10move 9 onto 13move 4 over 18pile 17 onto 4move 4 onto 19pile 1 onto 6move 4 over 2move 20 onto 21pile 2 over 1move 7 over 7pile 10 onto 21move 3 over 2pile 9 onto 15move 23 onto 10move 2 over 13move 4 over 4move 17 over 3pile 2 over 2pile 0 over 4pile 19 over 15pile 15 over 23pile 4 onto 18pile 12 over 1move 6 over 8move 11 over 17move 9 over 21move 7 onto 0pile 10 over 20pile 14 onto 8pile 18 onto 2move 5 onto 7move 4 onto 16move 19 over 21pile 13 onto 0move 23 onto 7pile 18 onto 7pile 3 onto 0pile 6 onto 10pile 11 onto 1move 2 over 23move 15 onto 10pile 12 over 4pile 13 onto 4move 4 onto 16pile 21 over 8pile 4 onto 23move 20 over 3move 3 over 7pile 22 over 18move 11 over 5pile 8 onto 21pile 17 onto 1pile 21 onto 2pile 23 over 10pile 3 onto 7move 4 over 22pile 11 onto 14pile 3 over 10pile 22 onto 8move 7 over 12pile 22 onto 21pile 13 onto 2move 5 over 5move 11 onto 10move 8 onto 13pile 8 onto 11pile 16 onto 2pile 8 over 20pile 7 over 13pile 15 onto 11move 16 onto 15move 23 onto 16move 2 over 19pile 9 over 16pile 22 over 2move 21 onto 13move 19 onto 4pile 21 over 11pile 8 onto 17pile 20 onto 3move 16 over 0pile 4 over 6pile 4 onto 18pile 7 over 12pile 12 over 15pile 7 onto 15move 22 onto 5move 6 onto 7move 11 onto 23move 2 over 14pile 15 over 23pile 5 over 8pile 6 onto 4pile 6 onto 5move 22 over 8pile 22 over 22pile 3 onto 4pile 2 onto 6pile 19 over 16pile 3 onto 20pile 22 over 23pile 19 onto 0pile 6 over 23pile 22 onto 10move 15 onto 20pile 18 onto 22move 4 onto 5pile 16 over 21pile 17 onto 14pile 16 over 17move 22 over 12pile 23 over 16move 5 over 17pile 13 over 7pile 21 onto 17move 20 onto 8move 4 over 16move 15 onto 3move 9 onto 22pile 7 over 2move 0 onto 16move 1 onto 14pile 12 onto 13pile 23 onto 18move 18 over 20move 21 onto 7move 14 onto 23move 2 onto 1move 22 over 14pile 1 over 8move 15 onto 19move 17 onto 6pile 21 onto 19pile 23 over 21pile 11 over 0move 20 over 5move 1 onto 19move 5 over 4pile 16 over 7pile 4 over 6move 16 onto 22pile 1 onto 11move 15 over 16move 16 over 18move 23 onto 21move 21 over 19pile 5 onto 2move 22 over 3move 22 over 4pile 11 over 18pile 23 onto 1pile 21 onto 20pile 10 over 13pile 18 over 22pile 0 onto 22move 22 over 8pile 12 over 3pile 1 over 12pile 2 onto 1pile 0 over 18pile 0 onto 23pile 23 onto 4move 8 over 12move 14 over 13pile 9 onto 1pile 20 over 14move 18 over 15move 14 onto 7pile 18 onto 15move 1 onto 17move 5 over 8pile 1 over 16pile 21 over 14move 16 onto 1move 10 over 14move 15 onto 5pile 3 onto 17pile 11 onto 13pile 21 onto 11pile 21 over 16move 11 onto 12move 9 over 12pile 4 over 14pile 21 over 22move 6 onto 4pile 15 onto 8pile 8 onto 11pile 16 over 16pile 9 over 22pile 15 over 11pile 10 over 7pile 14 onto 14move 5 onto 15pile 4 over 14move 12 over 11move 0 onto 22pile 20 over 14pile 17 over 17move 19 onto 9pile 2 onto 5pile 0 over 2move 23 onto 7move 22 over 13move 9 onto 7move 16 onto 21move 1 over 13move 3 over 5pile 20 over 7pile 12 over 8pile 14 over 23move 23 onto 7pile 8 over 7move 8 onto 12pile 15 onto 23move 10 over 11pile 6 over 22pile 0 over 5move 19 onto 8move 10 onto 4pile 16 over 1pile 13 onto 22pile 1 over 11pile 20 over 2pile 6 onto 23move 8 onto 0move 5 onto 22move 15 over 21pile 12 over 13move 8 onto 7move 18 over 7move 10 onto 1move 2 onto 18move 5 over 23pile 15 onto 5move 1 over 6pile 1 onto 0pile 1 onto 13move 3 onto 2move 0 onto 18pile 2 onto 23move 23 onto 22move 18 onto 17pile 21 over 1pile 22 over 5move 12 onto 4move 11 over 14pile 21 onto 16move 2 onto 9pile 10 onto 1pile 15 onto 6move 21 over 0move 18 over 12move 6 over 22pile 15 onto 1move 0 over 6move 20 onto 8move 21 over 5pile 10 onto 16pile 8 onto 23move 10 onto 8move 15 onto 22move 3 over 13pile 9 over 9pile 8 onto 20pile 19 onto 1move 12 over 20pile 16 onto 9pile 3 onto 14move 12 onto 15pile 2 onto 0move 7 onto 21pile 19 onto 19pile 15 onto 19pile 9 onto 21pile 1 onto 0move 4 over 6move 4 over 0pile 15 onto 10move 0 onto 22pile 13 onto 14pile 14 onto 6quit
#测试数据答案
0:1: 12: 23: 34:5: 5 22 06: 6 14 137: 78:9:10: 10 15 12 411: 1112:13:14:15:16:17: 1718: 1819: 1920: 20 821: 21 9 1622:23: 23
Migrated to