• <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.
            這道題是簡(jiǎn)單的BFS由于 對(duì)C++的不熟悉導(dǎo)致比賽的時(shí)候 怎么寫(xiě)一直猶豫不決剛才搞了搞C++終于寫(xiě)出來(lái)了 原來(lái)可以這樣寫(xiě)的

            #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) 評(píng)論(0)  編輯 收藏 引用

            只有注冊(cè)用戶(hù)登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問(wèn)   Chat2DB   管理


            <2009年3月>
            22232425262728
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            Friends

            OJ

            搜索

            •  

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            久久高潮一级毛片免费| 国产日韩欧美久久| 久久香蕉超碰97国产精品| 久久人人爽人人人人爽AV| 亚洲精品无码成人片久久| 国内精品久久久久久野外| 久久久久国产精品三级网| 午夜精品久久久久久中宇| 精品久久久久久久久中文字幕| 精品久久久久久无码免费| 久久精品国产99国产精品导航| 久久r热这里有精品视频| 伊人久久成人成综合网222| 久久精品嫩草影院| 久久人人爽人人人人爽AV| 久久精品人人做人人爽电影| 青青草原综合久久大伊人| 99久久www免费人成精品| 色欲av伊人久久大香线蕉影院| 国产AⅤ精品一区二区三区久久| 亚洲中文字幕无码久久综合网| 97精品伊人久久久大香线蕉| 久久亚洲精品成人AV| 亚洲精品成人久久久| 欧美日韩中文字幕久久伊人| 久久综合香蕉国产蜜臀AV| 亚洲国产综合久久天堂 | 久久夜色精品国产噜噜亚洲AV| 久久久久久久国产免费看| 大美女久久久久久j久久| 国产V亚洲V天堂无码久久久| A级毛片无码久久精品免费| 久久影院亚洲一区| 性做久久久久久久久久久| 久久久久亚洲av成人无码电影| 国産精品久久久久久久| 办公室久久精品| 国产精品亚洲美女久久久| 国产精品伊人久久伊人电影 | 久久亚洲国产成人影院网站| 2020最新久久久视精品爱 |