• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            ArcTan

            dfs
            隨筆 - 16, 文章 - 117, 評論 - 6, 引用 - 0
            數據加載中……

            SRM 500 DIV2 500PT(模擬)

            Problem Statement

                 NOTE: This problem statement contains images that may not display properly if viewed outside of the applet.

            We had a rectangular grid that consisted of W x H square cells. We placed a robot on one of the cells. The robot then followed the rules given below.
            • Initially, the robot is facing east.
            • The robot moves in steps. In each step it moves to the adjacent cell in the direction it currently faces.
            • The robot may not leave the grid.
            • The robot may not visit the same cell twice. (This also means that it may not reenter the starting cell.)
            • If a step forward does not cause the robot to break the above rules, the robot takes the step.
            • Otherwise, the robot rotates 90 degrees to the left (counter-clockwise) and checks whether a step forward still breaks the above rules. If not, the robot takes the step and continues executing this program (still rotated in the new direction).
            • If the rotation left did not help, the robot terminates the execution of this program.
            • We can also terminate the execution of the program manually, at any moment.
            For example, the following seven images show a series of moves made by the robot in a 12 x 11 board:



            We forgot the dimensions of the grid and the original (x,y) coordinates of the cell on which the robot was originally placed, but we do remember its movement. You are given a vector <int> moves. This sequence of positive integers shall be interpreted as follows: The robot performed moves[0] steps eastwards, turned left, performed moves[1] steps northwards, turned left, and so on. After performing the last sequence of steps, the robot stopped. (Either it detected that it should terminate, or we stopped it manually.) We are not sure if the sequence of moves is valid. If the sequence of moves is impossible, return -1. Else, return the minimum area of a grid in which the sequence of moves is possible. (I.e., the return value is the smallest possible value of the product of W and H.).

            Definition

                
            Class: RotatingBot
            Method: minArea
            Parameters: vector <int>
            Returns: int
            Method signature: int minArea(vector <int> moves)
            (be sure your method is public)
                

            Constraints

            - moves will contain between 1 and 50 elements, inclusive.
            - Each element of moves will be between 1 and 50, inclusive.

            Examples

            0)
                
            {15}
            Returns: 16
            The smallest valid board is a 16x1 board, with the robot starting on the west end of the board.
            1)
                
            {3,10}
            Returns: 44
            The smallest solution is to place the robot into the southwest corner of a 4 x 11 board.
            2)
                
            {1,1,1,1}
            Returns: -1
            This sequence of moves is not possible because the robot would return to its initial location which is forbidden.
            3)
                
            {9,5,11,10,11,4,10}
            Returns: 132
            These moves match the image from the problem statement.
            4)
                
            {12,1,27,14,27,12,26,11,25,10,24,9,23,8,22,7,21,6,20,5,19,4,18,3,17,2,16,1,15}
            Returns: 420

            5)
                
            {8,6,6,1}
            Returns: -1

            6)
                
            {8,6,6}
            Returns: 63

            7)
                
            {5,4,5,3,3}
            Returns: 30

            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.



            模擬題目,直接按照給定序列遍歷,如果遇到不合法的情況return -1。設定四個方向,mw,me,mn,ms,東北西南,初始為上下界。然后依次找到范圍。
            初始點(100,100)。
            最后的面積為(me-mw+1)*(ms-mn+1)

            沒有考慮完全啊,思維還是不嚴謹不完整,就WA了一組數據,昨晚做就悲劇了!!!!
            我是弱菜,繼續努力!

            不錯的模擬題目,需要考慮的東西很多!
            #include <cstdio>
            #include 
            <cstdlib>
            #include 
            <cstring>
            #include 
            <cmath>
            #include 
            <ctime>
            #include 
            <cassert>
            #include 
            <iostream>
            #include 
            <sstream>
            #include 
            <fstream>
            #include 
            <map>
            #include 
            <set>
            #include 
            <vector>
            #include 
            <queue>
            #include 
            <algorithm>
            #define min(x,y) (x<y?x:y)
            #define max(x,y) (x>y?x:y)
            #define swap(t,x,y) (t=x,x=y,y=t)
            #define clr(list) memset(list,0,sizeof(list))

            using namespace std;
            bool maps[205][205];
            int go[4][2]={{1,0},{0,-1},{-1,0},{0,1}};
            class RotatingBot{
            public:
                
            int minArea(vector <int> moves){
                    
            int n=moves.size();
                    
            int me=1000,mw=0,mn=0,ms=1000;
                    
            int tmp;
                    
            int dir;
                    
            int x,y,xx,yy;
                    clr(maps);
                    maps[
            100][100]=1;
                    x
            =100,y=100,dir=0;
                    
            for (int i=0;i<n ;i++)
                    {
                        tmp
            =moves[i];
                        
            for (int j=0;j<tmp;j++)
                        {
                            xx
            =x+go[dir][0];yy=y+go[dir][1];
                            
            if (maps[xx][yy] || (xx<mw || xx>me || yy<mn || yy>ms))
                                
            return -1;
                            
            else
                            {
                                maps[xx][yy]
            =1;
                                x
            =xx;y=yy;
                            }
                        }
                        xx
            =x+go[dir][0];yy=y+go[dir][1];
                        
            if (!maps[xx][yy])
                        {
                            
            if (dir==0)
                                
            if (me==1000)
                                    me
            =x;
                                
            else
                                    
            if (x<me && i<n-1)
                                        
            return -1;
                            
            if (dir==1)
                                
            if (mn==0)
                                    mn
            =y;
                                
            else if (y>mn && i<n-1)
                                    
            return -1;
                            
            if (dir==2)       //這里WA了testing 5 & 6
                                
            if (mw==0 && x<=100)
                                    mw
            =x;
                                
            else
                                    
            if (x>mw && i<n-1)
                                        
            return -1;
                            
            if (dir==3)            //最后栽在這里了
                                
            if (ms==1000 && y>=100)  
                                    ms
            =y;
                                
            else if ((y<ms || y<100&& i<n-1)
                                    
            return -1;
                        }
                        dir
            =(dir+1% 4;
                    }
                 
            //   return mw;
                    if (mw==0)
                        mw
            =100;
                    
            if (mn==0)
                        mn
            =100;
                    
            if (ms==1000)
                        ms
            =100;
                    
            return (me-mw+1)*(ms-mn+1);
                }
            };

            posted on 2012-07-22 10:10 wangs 閱讀(220) 評論(0)  編輯 收藏 引用 所屬分類: Topcoder

            久久精品国产久精国产思思| 久久亚洲综合色一区二区三区| 久久精品中文字幕一区| 内射无码专区久久亚洲| 国产69精品久久久久9999APGF | 久久er国产精品免费观看8| 欧美激情精品久久久久久久九九九| 一本色道久久88综合日韩精品| 精品久久无码中文字幕| 久久久久亚洲爆乳少妇无| 久久久无码精品亚洲日韩蜜臀浪潮| 精品无码久久久久久久久久| 久久久一本精品99久久精品66| 久久久久久久国产免费看| 久久99国产精品久久99| 亚洲va中文字幕无码久久| 理论片午午伦夜理片久久| 久久精品国产影库免费看| 欧洲成人午夜精品无码区久久| 久久人人爽人人爽AV片| 97久久精品人人做人人爽| 久久精品国产亚洲AV大全| 国内精品久久久久久久久电影网| 久久亚洲天堂| 久久精品亚洲福利| 国产免费福利体检区久久| 狠狠色丁香久久综合婷婷| 人人狠狠综合久久88成人| 新狼窝色AV性久久久久久| 久久香综合精品久久伊人| 亚洲&#228;v永久无码精品天堂久久 | 亚洲v国产v天堂a无码久久| 久久精品国产精品亚洲下载| 亚洲伊人久久大香线蕉苏妲己| 久久国产成人精品麻豆| 91久久婷婷国产综合精品青草| 国产亚洲色婷婷久久99精品| 2021少妇久久久久久久久久| 久久99国产亚洲高清观看首页| 99久久免费国产特黄| 久久电影网一区|