• <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>
            posts - 74,  comments - 33,  trackbacks - 0

            Problem Statement

            ???? According to research conducted recently, listening to classical music increases one's mental abilities, while listening to metal decreases them. Now, yet another experiment is being conducted to try to prove or disprove this statement.

            In this new experiment, a mouse is placed in a rectangular maze consisting of NxM squares. Each square either contains a wall or is empty. The maze is structured in such a way that for any two empty squares, there exists exactly one path between them. A path is a sequence of pairwise distinct empty squares such that every two consecutive squares are neighboring. Two squares are considered neighboring if they share a common edge.

            One of the empty squares in the maze contains a piece of cheese. The mouse's goal is to reach that square without visiting the same square twice. The mouse can only move between neighboring squares. Since the mouse has been listening to classical music for a week, he is extremely intelligent and guaranteed to achieve his goal.

            As the mouse moves from his starting point to the cheese, he may encounter some squares where he must choose between several neighboring squares to continue. This happens when the mouse steps into a square which has more than one neighboring empty square, excluding the square from which he came, or when he has more than one neighboring empty square at the start. These situations are called "decisions" and the mouse will always make the right choice.

            You are given a vector <string> maze representing the maze. It contains N elements, each containing M characters. Empty squares are denoted by '.', walls are denoted by uppercase 'X', the mouse's starting point is denoted by 'M', and the square containing the cheese is denoted by '*'. Return the number of decisions the mouse will make on his way to the cheese.

            Definition

            ????
            Class: MazeWanderingEasy
            Method: decisions
            Parameters: vector <string>
            Returns: int
            Method signature: int decisions(vector <string> maze)
            (be sure your method is public)
            ????

            Constraints

            - maze will contain between 1 and 50 elements, inclusive.
            - Each element of maze will contain between 1 and 50 characters, inclusive.
            - Elements of maze will be of the same length.
            - maze will contain only '.', 'X', 'M' or '*' characters.
            - There will be exactly one '*' character in maze.
            - There will be exactly one 'M' character in maze.
            - For every pair of empty squares in the maze, there will exist exactly one path between them.

            Examples

            0)
            ????
            {"*.M"}
            Returns: 0
            From each square, the mouse can only move to one other square, so he never has to make any decisions.
            1)
            ????
            {"*.M",
             ".X."}
            Returns: 1
            The mouse has to make a decision right at the start.
            2)
            ????
            {"...",
             "XMX",
             "..*"}
            Returns: 2
            The mouse makes decisions at both squares before reaching the cheese.
            3)
            ????
            {".X.X......X",
             ".X*.X.XXX.X",
             ".XX.X.XM...",
             "......XXXX."}
            Returns: 3
            4)
            ????
            {"..........*",
             ".XXXXXXXXXX",
             "...........",
             "XXXXXXXXXX.",
             "M.........."}
            Returns: 0

            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.
            這道題是簡單的BFS由于 對C++的不熟悉導致比賽的時候 怎么寫一直猶豫不決剛才搞了搞C++終于寫出來了 原來可以這樣寫的

            #include < cstdio >
            #include
            < vector >
            #include
            < queue >
            #include
            < string >
            #include
            < cstring >
            #define ?MAXN?120
            using ? namespace ?std;
            const ? int ?dir[ 4 ][ 2 ] = { { - 1 , 0 } , { 1 , 0 } , { 0 , - 1 } , { 0 , 1 } } ;
            struct ?NODE {
            ????
            int ?x,y,sum;????
            }
            pt;
            queue
            < NODE > Q;
            class ?MazeWanderingEasy {
            ????
            public ?:
            ????????
            int ?decisions(vector < string > ?maze) {
            ????????????
            int ?n,m,i,j,all,res;
            ????????????n
            = maze.size();m = maze[ 0 ].length();
            ????????????
            while ( ! Q.empty())Q.pop();
            ????????????
            bool ?mark[MAXN][MAXN];
            ????????????memset(mark,
            0 , sizeof (mark));
            ????????????
            for (i = 0 ;i < n;i ++ )
            ????????????????
            for (j = 0 ;j < m;j ++ )
            ????????????????????
            if (maze[i][j] == ' M ' ) {
            ????????????????????????pt.x
            = i,pt.y = j,pt.sum = 0 ;
            ????????????????????????Q.push(pt);
            ????????????????????????
            break ;
            ????????????????????}

            ????????????mark[i][j]
            = true ;
            ????????????
            while ( ! Q.empty()) {
            ????????????????pt
            = Q.front();
            ????????????????
            int ?x = pt.x,y = pt.y;
            ????????????????
            if (maze[x][y] == ' * ' ) {
            ????????????????????res
            = pt.sum;
            ????????????????????
            break ;
            ????????????????}

            ????????????????
            for (all = i = 0 ;i < 4 ;i ++ ) {
            ????????????????????
            int ?nx = x + dir[i][ 0 ];
            ????????????????????
            int ?ny = y + dir[i][ 1 ];
            ????????????????????
            if (nx < n && nx >= 0 && ny < m && ny >= 0 &&! mark[nx][ny] && maze[nx][ny] == ' . ' )all ++ ;????
            ????????????????}

            ????????????????
            for (all = i = 0 ;i < 4 ;i ++ ) {
            ????????????????????
            int ?nx = x + dir[i][ 0 ];
            ????????????????????
            int ?ny = y + dir[i][ 1 ];
            ????????????????????
            if (nx < n && nx >= 0 && ny < m && ny >= 0 &&! mark[nx][ny] && maze[nx][ny] == ' . ' ) {
            ????????????????????????mark[nx][ny]
            = true ;
            ????????????????????????pt.x
            = nx,pt.y = ny,pt.sum = Q.front().sum + all - 1 ;
            ????????????????????}
            ????
            ????????????????}

            ????????????????Q.pop();
            ????????????}

            ????????????
            return ?res;
            ????????}
            ????
            }
            ;


            ?

            posted on 2009-05-12 22:10 KNIGHT 閱讀(194) 評論(0)  編輯 收藏 引用
            <2009年5月>
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            Friends

            OJ

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            好久久免费视频高清| 久久免费线看线看| 久久人人青草97香蕉| 久久丫精品国产亚洲av不卡| 国产精品伦理久久久久久| 久久久久久久久久久久久久| 久久国产一区二区| 国产精品激情综合久久| 久久久精品国产| 精品久久久久久国产| 伊人久久精品影院| 国产精品熟女福利久久AV| 四虎影视久久久免费| 久久久精品无码专区不卡| 精品一区二区久久久久久久网站| 94久久国产乱子伦精品免费| 99re这里只有精品热久久| 久久综合给合久久狠狠狠97色 | 精品久久久久久久| 久久久久亚洲av成人无码电影 | 久久精品亚洲日本波多野结衣| 国产精品成人99久久久久91gav| 久久精品国产亚洲av麻豆图片| 日本精品久久久久中文字幕 | 777久久精品一区二区三区无码| 大香伊人久久精品一区二区| 久久亚洲电影| 国产高清美女一级a毛片久久w| 日韩人妻无码精品久久免费一| 久久中文字幕人妻丝袜| 久久免费99精品国产自在现线| 久久精品国产精品青草| 国产精品无码久久久久久| 91精品国产91久久久久久青草| 亚洲AV无码成人网站久久精品大| 久久WWW免费人成一看片| 性做久久久久久久久久久| 久久亚洲AV无码西西人体| 免费一级欧美大片久久网| 久久综合视频网站| 欧美粉嫩小泬久久久久久久 |