GOOGLE挑战赛练习题1

cisco

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",

"...................." }



我的程序（lack of expection handler）：

1. 
   
2. public class DrawLines {
   
3.         // current cursor position
   
4.         private int xPos, yPos;
   
5. 
   
6.         private int direction;
   
7. 
   
8.         private char[][] canvas;
   
9. 
   
10.         public DrawLines() {
    
11.                 xPos = 0;
    
12.                 yPos = 0;
    
13.                 // initial drawing direction downwards
    
14.                 direction = 270;
    
15.                 canvas = new char[20][20];
    
16.         }
    
17. 
    
18.         private void initCanvas() {
    
19.                 for (int i = 0; i < 20; i++)
    
20.                         for (int j = 0; j < 20; j++)
    
21.                                 canvas[i][j] = '.';
    
22.         }
    
23. 
    
24.         public String[] excute(String[] commands) {
    
25.                 initCanvas();
    
26.                 for (int i = 0; i < commands.length; i++) {
    
27.                         if (commands[i].equals("LEFT")) {
    
28.                                 // when come cross "LEFT", turn 90 degrees couter-clockwise
    
29.                                 direction += 90;
    
30.                                 if (direction == 360)
    
31.                                         direction = 0;
    
32.                         } else {
    
33.                                 int len = Integer.parseInt(commands[i].split(" ")[1]);
    
34.                                 switch (direction) {
    
35.                                 case 0:
    
36.                                         // draw from left to right
    
37.                                         for (int j = 0; j <= len; j++)
    
38.                                                 canvas[xPos][yPos++] = 'X';
    
39.                                         yPos--;
    
40.                                         break;
    
41.                                 case 90:
    
42.                                         // draw from down to up
    
43.                                         for (int j = 0; j <= len; j++)
    
44.                                                 canvas[xPos--][yPos] = 'X';
    
45.                                         xPos++;
    
46.                                         break;
    
47.                                 case 180:
    
48.                                         // draw from right to left
    
49.                                         for (int j = 0; j <= len; j++)
    
50.                                                 canvas[xPos][yPos--] = 'X';
    
51.                                         yPos++;
    
52.                                         break;
    
53.                                 case 270:
    
54.                                         // draw from up to down
    
55.                                         for (int j = 0; j <= len; j++)
    
56.                                                 canvas[xPos++][yPos] = 'X';
    
57.                                         xPos--;
    
58.                                         break;
    
59.                                 }
    
60.                         }
    
61.                 }
    
62.                 String[] s = new String[20];
    
63.                 for (int i = 0; i < 20; i++)
    
64.                         s[i] = new String(canvas[i]);
    
65.                 return s;
    
66.         }
    
67. 
    
68.         public static void main(String[] args) {
    
69.                 String[] cmds = { "LEFT", "FORWARD 19", "LEFT", "LEFT", "LEFT",
    
70.                                 "FORWARD 18", "LEFT", "LEFT", "LEFT", "FORWARD 17", "LEFT",
    
71.                                 "LEFT", "LEFT", "FORWARD 16", "LEFT", "LEFT", "LEFT",
    
72.                                 "FORWARD 15", "LEFT", "LEFT", "LEFT", "FORWARD 14", "LEFT",
    
73.                                 "LEFT", "LEFT", "FORWARD 13", "LEFT", "LEFT", "LEFT",
    
74.                                 "FORWARD 12", "LEFT", "LEFT", "LEFT", "FORWARD 11", "LEFT",
    
75.                                 "LEFT", "LEFT", "FORWARD 10", "LEFT", "LEFT", "LEFT",
    
76.                                 "FORWARD 9", "LEFT", "LEFT", "LEFT", "FORWARD 8", "LEFT",
    
77.                                 "LEFT", "LEFT", "FORWARD 7" };
    
78.                 DrawLines drawLines = new DrawLines();
    
79.                 String[] s = drawLines.excute(cmds);
    
80.                 for (int i = 0; i < 20; i++)
    
81.                         System.out.println(s[i]);
    
82.         }
    
83. }
    

复制代码

大家都来讨论吧，看有什么其它算法

无双

我的 只需要把对应的if 0去掉就可以
[PHP]

#if 0
#include <vector>
#include <string>
using namespace std;
static int matrixtable[]={    0,    1,    2,    9,    16,    25,    36,    49,    64,    81,    100,    121};

class MatrixTool{
    public:
        vector <string> convert(string s){
            vector<string>  res;
            int len = s.length();
            unsigned long i =0;
            for( ; i<12; i++ ){
                if( len == matrixtable )
                    goto end;
                else if( len < matrixtable )
                    return res;
            }
            for( ;;i++ ){
                unsigned long val   = i * i;
                if( len == val )
                    goto end;
                else if( len < val )
                    return res;
            }
end:
            const char* p = s.c_str();
            for(int j = 0; j < len ; j+=i,p+=i ){
                res.push_back(string(p,i));
            }
            return res;
        }
};
#endif

#if 0
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
using namespace std;

#define LEFT_CMD        "LEFT"
#define FORWARD_CMDSIZE strlen("FORWARD")

class DrawLines{
    public:
        vector<string> execute(vector<string> commands){
            char        canvas[20][20];
            memset(canvas,'.',sizeof(canvas));

            int     x    = 0;    //  current axes
            int     y    = 0;    //  current axes
            int     curangle= 0;    //  current angle,0:0, 1:90,2:180,3:270,
            int i       =0;
            for(vector<string>::iterator iter = commands.begin(); iter != commands.end(); iter++ ){
                const char* p = iter->c_str();
                if( !strcmp(LEFT_CMD,p) ){
                    if( curangle == 3 )     curangle    = 0;
                    else                    curangle    ++;
                }
                else {
                    i   =0;
                    int step        = atoi(p + FORWARD_CMDSIZE );
                    canvas[y][x]  = 'X';
                    switch(curangle){
                        case 0:
                            for(;i<step;i++)
                                canvas[++y][x]  = 'X';
                            break;  
                        case 1:         
                            for(;i<step;i++)
                                canvas[y][++x]  = 'X';
                            break;  
                        case 2:
                            for(;i<step;i++)
                                canvas[--y][x]  = 'X';
                            break;  
                        default:
                            for(;i<step;i++)
                                canvas[y][--x]  = 'X';
                            break;  
                    }
                }
            }

            vector<string>  canvas_str;
            for(i =0;i<20;i++)
                canvas_str.push_back(string(canvas,20));
            return canvas_str;
        }
};

DrawLines       d;
void check(const char** params)
{
    vector<string>  s;
    for(;*params;params++){
        printf("\t%s",*params);
        s.push_back(string(*params));
    }
        printf("\noutput is:\n");
    vector<string>  o   = d.execute(s);
    for( vector<string>::iterator iter = o.begin(); iter != o.end(); iter ++ )
        printf("\t%s\n",iter->c_str());
}

int main()
{
const char* p1[]   =   {"FORWARD 19", "LEFT", "FORWARD 19", "LEFT", "FORWARD 19", "LEFT", "FORWARD 19",NULL};
const char* p2[]   =   {"LEFT", "LEFT", "LEFT", "LEFT", "LEFT", "LEFT", "LEFT", "LEFT",NULL};
const char* p3[]   =   {"FORWARD 1",NULL};
const char* p4[]   =   {"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",NULL};
    check(p1);
    check(p2);
    check(p3);
    check(p4);
    return 0;
}

#endif
[/PHP]