羽毛球

生活在别处

导航

<2008年9月>
日一二三四五六
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

统计

留言簿(29)

随笔分类

随笔档案

文章分类

文章档案

搜索

最新评论

阅读排行榜

评论排行榜

Google™ Code Jam - 中国编程挑战赛模拟题一

 Google™ Code Jam - 中国编程挑战赛 
http://www.topcoder.com/gcjc_zh

 你有用技术改变世界的梦想吗？你有挑战难度的决心吗？你想和国内计算机精英一决高下吗？全球编程界知名的“Google编程挑战赛Code Jam”即将登陆中国。这项比赛每年都是全球计算机界的一次盛事。今年 Google 首次专门为中国举办这项比赛，旨在弘扬计算机科学的艺术，推进中国计算机编程教育，鼓励并嘉奖中国顶级编程人才。

竞赛的题目具有相当的挑战性，竞赛奖品也非常丰厚。 有志之士可借此机会一展才能，成为脱颖而出的中国最佳。

这里有极富挑战性的题目，高科技的奖品，以及令人赞叹的荣耀，你还在等什么？

趁周末，申请一个帐号，进入Try了一下模拟题。
题目是英文描述：

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 vector <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 vector <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: vector <string>
Returns: vector <string>
Method signature: vector <string> execute(vector <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",
 "...................." }

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.


我的代码：

#include <string>
#include <vector>

using namespace std;

const char* const pcstrBlankLine = "..";

const char* const CMD_FORWARD = "FORWARD";
const int SIZE_FORWARD = strlen(CMD_FORWARD);
const char* const CMD_LEFT = "LEFT";
const int SIZE_LEFT = strlen(CMD_LEFT);

const char CANVAS_BLACK = 'X';

class DrawLines
{
public:
    enum
    {
        TYPE_NONE = 0,
        TYPE_FORWARD = 1,
        TYPE_LEFT = 2,

        CANVAS_WIDTH = 20,
        CANVAS_HEIGHT = 20,

        DIRECT_DOWN = 0,
        DIRECT_LEFT = 1,
        DIRECT_UP = 2,
        DIRECT_RIGHT = 3
    };

    vector<string> execute(vector<string> commands);

    void ExcuteOneCommand(const string& cmd);
    int GetComType(const string& strCmd, int& iStep);

    DrawLines() : m_iDirection(DIRECT_DOWN), 
        m_iCurrHorizonPos(0), 
        m_iCurrVerticalPos(0)
    {
    }

public:
    vector<string> m_paintedCanvas;

    int m_iDirection;
    int m_iCurrHorizonPos;
    int m_iCurrVerticalPos;
};

vector<string> DrawLines::execute(vector<string> commands)
{
    m_paintedCanvas.clear();
    int i = 0;
    for (i = 0; i < CANVAS_HEIGHT; i++)
    {
        m_paintedCanvas.push_back(pcstrBlankLine);
    }

    for (i = 0; i < commands.size(); i++)
    {
        ExcuteOneCommand(commands[i]);
    }

    return m_paintedCanvas;
}

void DrawLines::ExcuteOneCommand(const string& cmd)
{
    int iStep = 0;
    if (GetComType(cmd, iStep) == TYPE_FORWARD)
    {
        if (iStep <= 0)
        {
            return;
        }

        //Drawline
        if (DIRECT_DOWN == m_iDirection)
        {
            int nReachPos = (m_iCurrVerticalPos+iStep < CANVAS_HEIGHT)?(m_iCurrVerticalPos+iStep):CANVAS_HEIGHT-1;
            for (int i = m_iCurrVerticalPos; i <= nReachPos; i++)
            {
                m_paintedCanvas[i].at(m_iCurrHorizonPos) = CANVAS_BLACK;
            }

            m_iCurrVerticalPos = nReachPos;
        }
        else if (DIRECT_UP == m_iDirection)
        {
            int nReachPos = (m_iCurrVerticalPos-iStep >= 0)?(m_iCurrVerticalPos-iStep):0;
            for (int i = m_iCurrVerticalPos; i >= nReachPos; i--)
            {
                m_paintedCanvas[i].at(m_iCurrHorizonPos) = CANVAS_BLACK;
            }

            m_iCurrVerticalPos = nReachPos;
        }
        else if (DIRECT_LEFT == m_iDirection)
        {
            int nReachPos = (m_iCurrHorizonPos+iStep < CANVAS_HEIGHT)?(m_iCurrHorizonPos+iStep):CANVAS_HEIGHT-1;
            for (int i = m_iCurrHorizonPos; i <= nReachPos; i++)
            {
                m_paintedCanvas[m_iCurrVerticalPos].at(i) = CANVAS_BLACK;
            }

            m_iCurrHorizonPos = nReachPos;
        }
        else if (DIRECT_RIGHT == m_iDirection)
        {
            int nReachPos = (m_iCurrHorizonPos-iStep >= 0)?(m_iCurrHorizonPos-iStep):0;
            for (int i = m_iCurrHorizonPos; i >= nReachPos; i--)
            {
                m_paintedCanvas[m_iCurrVerticalPos].at(i) = CANVAS_BLACK;
            }

            m_iCurrHorizonPos = nReachPos;
        }
    }
    else if (GetComType(cmd, iStep) == TYPE_LEFT)
    {
        if (DIRECT_RIGHT == m_iDirection)
        {
            m_iDirection = DIRECT_DOWN;
        }
        else
        {
            m_iDirection++;
        }
    }
}

int DrawLines::GetComType(const string& strCmd, int& iStep)
{
    const char* pstrCmd = strCmd.c_str();
    if (strncmp(pstrCmd, CMD_FORWARD, SIZE_FORWARD) == 0)
    {
        pstrCmd += SIZE_FORWARD + 1; 
        iStep = atoi(pstrCmd);
        return TYPE_FORWARD;
    }
    else if (strncmp(pstrCmd, CMD_LEFT, SIZE_LEFT) == 0)
    {
        return TYPE_LEFT;
    }
    
    return TYPE_NONE;
}


得分取决于正确程度和总共花的时间。

posted on 2005-11-26 22:15 Michael 阅读(3398) 评论(2)  编辑 收藏

评论

# re: Google™ Code Jam - 中国编程挑战赛模拟题一 2005-11-26 23:46 清风雨

我看到过java版本的这道题目，不过，没看过C++版本的。
不过，他不知道允许不用string不？

# re: Google™ Code Jam - 中国编程挑战赛模拟题一 2005-11-27 16:09 my12doom

这些是不是太简单了？

标题  
姓名  
主页
验证码 *
内容   
  登录  使用高级评论  Top
[使用Ctrl+Enter键可以直接提交]