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 阅读(187) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


<2009年2月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
1234567

常用链接

留言簿(8)

随笔档案

文章档案

Friends

OJ

搜索

  •  

最新评论

阅读排行榜

评论排行榜