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) |
|
| |
|
|
Returns: 0
|
| From each square, the mouse can only move to one other square, so he never has to make any decisions. |
|
|
| 1) |
|
| |
|
|
Returns: 1
|
| The mouse has to make a decision right at the start. |
|
|
| 2) |
|
| |
|
|
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 阅读(185)
评论(0) 编辑 收藏 引用