Google中国编程挑战赛模拟题(答案)

出处：CSDN.NET[ 2005-11-25 14:08:51 ] 作者：netsafe提供 责任编辑：lujiezhen

* 资格赛的编码阶段以计时赛形式出现，参赛者会抽到5组题中的1组，每组题有2道难度不同的题目，难度高的题目分数较高。题目的得分情况取决于解决方案的编译成功与否，以及从打开题目到提交方案所耗费的时间长短。参赛者有60分钟可以完成全部的2题或其中1题。60分钟从打开第1题开始计时，编码窗口内的计时器会倒计时直至时间结束。参加资格赛的选手如果在这60分钟内来熟悉资格赛，就会花去一定的时间，实际的编程时间就只有不到60 分钟了。
* 资格赛系统测试阶段只对所有提交了的方案代码进行测试。如果TopCoder系统测试发现代码存在缺陷，则提交代码的选手将被扣除此题的所有分数。系统自动测试会输入一系列参数值，验证提交方案返回结果的正确性，如果与期望结果不匹配，则方案被认为有误。每一题的所有输入测试数据都相同，会输入到不同的提交方案中进行测试。
今天看csdn得到Google Code Jam 的消息.也注册了一个帐户进去玩玩.全是英文，头疼.随便打开一个房间选了一道250分的题目：
Problem Statement
A simple line drawing program uses a blank 20 x 20 pixel canvas and a directional cursor that starts at the upper left corner pointing straight down. The upper left corner of the canvas is at (0, 0) and the lower right corner is at (19, 19). You are given a string[], commands, each element of which contains one of two possible commands. A command of the form "FORWARD x" means that the cursor should move forward by x pixels. Each pixel on its path, including the start and end points, is painted black. The only other command is "LEFT", which means that the cursor should change its direction by 90 degrees counterclockwise. So, if the cursor is initially pointing straight down and it receives a single "LEFT" command, it will end up pointing straight to the right. Execute all the commands in order and return the resulting 20 x 20 pixel canvas as a string[] where character j of element i represents the pixel at (i, j). Black pixels should be represented as uppercase ‘X‘ characters and blank pixels should be represented as ‘.‘ characters.
Definition
Class:  DrawLines
Method:  execute
Parameters:  string[]
Returns:  string[]
Method signature:  string[] execute(string[] commands)
(be sure your method is public)
Notes
-  The cursor only paints the canvas if it moves (see example 1).
Constraints
-  commands will contain between 1 and 50 elements, inclusive.
-  Each element of commands will be formatted as either "LEFT" or "FORWARD x" (quotes for clarity only), where x is an integer between 1 and 19, inclusive, with no extra leading zeros.
-  When executing the commands in order, the cursor will never leave the 20 x 20 pixel canvas.
Examples
0)
{"FORWARD 19", "LEFT", "FORWARD 19", "LEFT", "FORWARD 19", "LEFT", "FORWARD 19"}
Returns:
{"XXXXXXXXXXXXXXXXXXXX",
"X..................X",
"X..................X",
"X..................X",
"X..................X",
"X..................X",
"X..................X",
"X..................X",
"X..................X",
"X..................X",
"X..................X",
"X..................X",
"X..................X",
"X..................X",
"X..................X",
"X..................X",
"X..................X",
"X..................X",
"X..................X",
"XXXXXXXXXXXXXXXXXXXX" }
This sequence of commands draws a 20 x 20 outline of a square. The cursor is initially at (0, 0) pointing straight down. It then travels to (0, 19) after the first FORWARD command, painting each pixel along its path with a ‘*‘. It then rotates 90 degrees left, travels to (19, 19), rotates 90 degrees left, travels to (19, 0), rotates 90 degrees left, and finally travels back to (0, 0).
1)
{"LEFT", "LEFT", "LEFT", "LEFT", "LEFT", "LEFT", "LEFT", "LEFT"}
Returns:
{"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"...................." }
The cursor spins round and round, but never actually paints any pixels. The result is an empty canvas.
2)
{"FORWARD 1"}
Returns:
{"X...................",
"X...................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"....................",
"...................." }
Going forward by one pixel creates a line that is 2 pixels long because both the start and end points are painted.
3)
{"LEFT", "FORWARD 19", "LEFT", "LEFT", "LEFT",
"FORWARD 18", "LEFT", "LEFT", "LEFT", "FORWARD 17",
"LEFT", "LEFT", "LEFT", "FORWARD 16", "LEFT",
"LEFT", "LEFT", "FORWARD 15", "LEFT", "LEFT", "LEFT",
"FORWARD 14", "LEFT", "LEFT", "LEFT", "FORWARD 13",
"LEFT", "LEFT", "LEFT", "FORWARD 12", "LEFT", "LEFT",
"LEFT", "FORWARD 11", "LEFT", "LEFT", "LEFT", "FORWARD 10",
"LEFT", "LEFT", "LEFT", "FORWARD 9", "LEFT", "LEFT",
"LEFT", "FORWARD 8", "LEFT", "LEFT", "LEFT", "FORWARD 7"}
Returns:
{"XXXXXXXXXXXXXXXXXXXX",
"...................X",
"..XXXXXXXXXXXXXXXX.X",
"..X..............X.X",
"..X.XXXXXXXXXXXX.X.X",
"..X.X..........X.X.X",
"..X.X.XXXXXXXX.X.X.X",
"..X.X.X........X.X.X",
"..X.X.X........X.X.X",
"..X.X.X........X.X.X",
"..X.X.X........X.X.X",
"..X.X.X........X.X.X",
"..X.X.X........X.X.X",
"..X.X.X........X.X.X",
"..X.X.XXXXXXXXXX.X.X",
"..X.X............X.X",
"..X.XXXXXXXXXXXXXX.X",
"..X................X",
"..XXXXXXXXXXXXXXXXXX",
"...................." }
(以上题目来自互关网）
好象正式比赛是一小时做三道题目.我肯定是不行了.我光把题看明白就过去20多分钟了。而且还用了字典.不过题目看懂后感觉还是很简单的.下边是我的算法: