• <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

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            国产精品gz久久久| 97久久婷婷五月综合色d啪蜜芽| 无码国产69精品久久久久网站| 伊人久久综合精品无码AV专区| 国产成年无码久久久久毛片| segui久久国产精品| 老男人久久青草av高清| 国内精品久久九九国产精品| 午夜精品久久久内射近拍高清| 日本久久久久亚洲中字幕| 国产成人AV综合久久| 无码人妻少妇久久中文字幕蜜桃| 日本三级久久网| 中文字幕无码精品亚洲资源网久久 | 麻豆精品久久精品色综合| 国产精品无码久久综合网| 色狠狠久久AV五月综合| 亚洲欧美日韩久久精品| 久久99精品久久久久久| 伊人色综合久久天天人手人婷| 久久99精品国产99久久6| 久久久亚洲欧洲日产国码二区| 色天使久久综合网天天| 久久亚洲高清综合| 国产精品美女久久久免费| 久久av无码专区亚洲av桃花岛| 老司机午夜网站国内精品久久久久久久久 | 国产精品欧美亚洲韩国日本久久| 熟妇人妻久久中文字幕| 久久亚洲日韩看片无码| 亚洲国产成人精品女人久久久| 国产精品免费久久久久影院| 99精品伊人久久久大香线蕉| 久久精品国产99国产精偷 | 国产午夜久久影院| 97久久精品无码一区二区| 日产精品久久久久久久性色| 蜜臀久久99精品久久久久久小说| 中文字幕乱码人妻无码久久| 一本久道久久综合狠狠爱| 97精品依人久久久大香线蕉97|