首页 > ACM题库 > HDU-杭电 > hdu 2755 Logo 2[解题报告]hoj
2014
02-14

hdu 2755 Logo 2[解题报告]hoj

Logo 2

问题描述 :

Logo is a programming language built around a turtle. Commands in the language cause the turtle to move. The turtle has a pen attached to it. As the turtle moves, it draw lines on the page. The turtle can be programmed to draw interesting pictures.

We are interested in making the turtle draw a picture, then return to the point that it started from. For example, we could give the turtle the following program:

fd 100 lt 120 fd 100 lt 120 fd 100

The command fd causes the turtle to move forward by the specified number of units. The command lt causes the turtle to turn left by the specified number of degrees. Thus the above commands cause the turtle to draw an equilateral triangle with sides 100 units long. Notice that after executing the commands, the turtle ends up in the same place as it started. The turtle understands two additional commands. The command bk causes the turtle to move backward by the specified number of units. The command rt causes the turtle to turn right by the specified number of degrees. The distances and angles in all commands are always non-negative integers.

Unfortunately, we have been messy in writing the program down, and cannot read our own writing. One of the numbers in the program is missing. Assuming the turtle ends up at the place that it started at the end of its journey, can you find the missing number?

输入:

The first line of each test chunk contains an integer specifying the number of test cases in this chunk to follow. Each test case starts with a line containing one integer, the number of commands to follow. The commands follow, one on each line. Each test case will contain no more than 1000 commands. The argument of each command is either an integer or a question mark (?). There will be exactly one question mark in each test case.
Please process to the end of the data file.

输出:

The first line of each test chunk contains an integer specifying the number of test cases in this chunk to follow. Each test case starts with a line containing one integer, the number of commands to follow. The commands follow, one on each line. Each test case will contain no more than 1000 commands. The argument of each command is either an integer or a question mark (?). There will be exactly one question mark in each test case.
Please process to the end of the data file.

样例输入:

1
5
fd 100
lt 120
fd ?
lt 120
fd 100
1
5
fd 100
lt 120
fd ?
lt 120
fd 100

样例输出:

100
100

Code
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
#define PI 3.14159265358979
#define EPSILON 1e-6
typedef struct Point
{
    double x,y;
    Point(double a = 0,double b = 0):x(a),y(b) {}
    Point(const Point & p):x(p.x),y(p.y) {}
    friend Point operator + (const Point &p1, const Point & p2)
    {
        return Point(p1.x+p2.x,p1.y+p2.y);
    }
    Point & operator += (const Point & p)
    {
        x += p.x;
        y += p.y;
        return *this;
    }
    friend Point operator * (const Point & p, int u)
    {
        return Point(p.x*u,p.y*u);
    }
    Point & operator = (const Point & p)
    {
        x = p.x;
        y = p.y;
        return * this;
    }
    friend bool operator == (const Point & p1, const Point & p2)
    {
        if(fabs(p1.x-p2.x)<EPSILON && fabs(p1.y-p2.y)<EPSILON)
            return true;
        return false;
    }

}Vector;
struct Logo
{
    char str[6];
    int u;
};

Logo ls[1000];
int num;
char cmd[6];

Point Test(double theta, Vector v,Point pt,int j,int degree)
{
    if(cmd[0] == 'l')
    { theta+=degree; v = Vector(cos(PI*theta/180),sin(PI*theta/180));}
    else
    { theta-=degree; v = Vector(cos(PI*theta/180),sin(PI*theta/180)); } 

    for(int k = j+1; k<num; k++)
    {
        int t = ls[k].u;
        switch(ls[k].str[0])
        {
        case 'f': pt += v*t; break;
        case 'b': pt += v*(-t); break;
        case 'l': theta+=t; v = Vector(cos(PI*theta/180),sin(PI*theta/180));
            break;
        case 'r': theta-=t; v = Vector(cos(PI*theta/180),sin(PI*theta/180));
            break;
        }
    }
    return pt;
}
int main()
{
    int test,i,j,k,t;

    char unit[128];
    while(scanf("%d",&test)==1)
    {
        for(i = 0; i<test; i++)
        {
            scanf("%d",&num);
            Point pt;
            Vector v(1,0);
            Vector vx;
            double theta = 0.0;
            for(j = 0; j<num; j++)
            {
                scanf("%s %s",cmd,unit);
                if(unit[0] == '?')
                    break;
                t = atoi(unit);
                switch(cmd[0])
                {
                case 'f': pt += v*t; break;
                case 'b': pt += v*(-t); break;
                case 'l': theta+=t; v = Vector(cos(PI*theta/180),sin(PI*theta/180));
                    break;
                case 'r': theta-=t; v = Vector(cos(PI*theta/180),sin(PI*theta/180));
                    break;
                }
            }
            for(k = j+1; k<num; k++)
            {
                scanf("%s %d",ls[k].str,&ls[k].u);
            }
            if(cmd[0] == 'l' || cmd[0] == 'r')
            {
                for(int degree = 0; degree < 360; degree++)
                {
                    if(Test(theta,v,pt,j,degree) == Point(0.0,0.0) )
                    {
                        printf("%d\n",degree);
                        break;
                    }
                }
            }
            else
            {
                vx = v;
    
                for(k = j+1; k<num; k++)
                {
                    t = ls[k].u;
                    switch(ls[k].str[0])
                    {
                    case 'f': pt += v*t; break;
                    case 'b': pt += v*(-t); break;
                    case 'l': theta+=t; v = Vector(cos(PI*theta/180),sin(PI*theta/180));
                        break;
                    case 'r': theta-=t; v = Vector(cos(PI*theta/180),sin(PI*theta/180));
                        break;
                    }
                }
                printf("%d\n",(int)(sqrt(pt.x*pt.x + pt.y*pt.y)+0.5));
            }
        }
    }
    return 0;
}

解题参考:http://www.cnblogs.com/longzhiri/articles/1559773.html


  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  2. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  3. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。