• <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年1月>
            28293031123
            45678910
            11121314151617
            18192021222324
            25262728293031
            1234567

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            Friends

            OJ

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久不见久久见免费影院www日本| 欧美一区二区久久精品| 精品久久久久中文字幕日本| 精品熟女少妇a∨免费久久| 国产国产成人精品久久| 99久久精品免费| 最新久久免费视频| 国产精品久久久久国产A级| 国产三级精品久久| 热re99久久精品国99热| 91精品国产色综久久| 亚洲中文字幕无码久久2020 | 久久婷婷五月综合97色直播| 久久经典免费视频| 99久久国产亚洲高清观看2024| 欧美伊人久久大香线蕉综合| 久久99精品久久久久久齐齐| 久久人爽人人爽人人片AV| 欧美日韩中文字幕久久久不卡 | 久久精品毛片免费观看| 久久久久久久久久免免费精品| 久久精品人人做人人妻人人玩 | 精品久久久久香蕉网| 久久天天躁夜夜躁狠狠躁2022| 国产午夜福利精品久久| 精品熟女少妇a∨免费久久| 久久久久精品国产亚洲AV无码| 久久精品无码一区二区日韩AV | 久久久久久精品免费免费自慰| 久久久久97国产精华液好用吗| 久久综合狠狠综合久久激情 | 韩国免费A级毛片久久| 2021久久精品国产99国产精品| 99精品国产综合久久久久五月天| 亚洲另类欧美综合久久图片区| 久久亚洲AV永久无码精品| 久久伊人色| 欧美亚洲国产精品久久| 久久精品成人欧美大片| 国产美女亚洲精品久久久综合| 成人久久免费网站|