• <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年3月>
            22232425262728
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            Friends

            OJ

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            国产精品久久久久久久 | 久久久这里有精品中文字幕| 久久夜色精品国产网站| 久久亚洲AV成人出白浆无码国产| 久久伊人精品一区二区三区| 久久精品国产亚洲AV忘忧草18| 偷偷做久久久久网站| 精品国产乱码久久久久软件| 97视频久久久| AV色综合久久天堂AV色综合在| 久久久青草久久久青草| 香蕉99久久国产综合精品宅男自| 久久精品一本到99热免费| 久久久久人妻一区二区三区vr| 国产69精品久久久久99尤物| 亚洲综合久久夜AV | 午夜不卡久久精品无码免费| 久久亚洲高清观看| 久久久国产打桩机| 国产AⅤ精品一区二区三区久久| 中文精品99久久国产 | 久久精品国产清高在天天线| 国产免费久久精品99久久| 波多野结衣AV无码久久一区| 国产精品午夜久久| 99久久精品午夜一区二区 | 青青草国产精品久久| 性欧美大战久久久久久久| 青青青国产成人久久111网站| 久久精品卫校国产小美女| 色综合合久久天天综合绕视看| 亚洲综合精品香蕉久久网| 国产亚洲美女精品久久久| 精品国产乱码久久久久久郑州公司| 久久大香萑太香蕉av| 久久久久亚洲AV无码专区网站| 国产成人精品久久亚洲高清不卡 | 久久亚洲精品国产精品| 少妇内射兰兰久久| 中文字幕乱码久久午夜| 国内精品九九久久精品|