Problem Statement
People enjoy mazes, but they also get them dirty. Arrows, graffiti, and chewing gum are just a few of the souvenirs people leave on the walls. You, the maze keeper, are assigned to whiten the maze walls. Each face of the wall requires one liter of paint, but you are only required to paint visible faces. You are given a map of the maze, and you must determine the amount of paint needed for the job.
The maze is described by a String[] maze, where each character can be either '#' (a wall) or '.' (an empty space). All '.' characters on the perimeter of the map are considered entrances to the maze. Upon entering the maze, one can only move horizontally and vertically through empty spaces, and areas that are not reachable by these movements are not considered visible. Each '#' represents a square block with four wall faces (each side of the square is a face). A face is visible if it is not directly adjacent to another wall (and is in a reachable area of the maze). For example, two adjacent blocks can have at most six visible faces since two of their faces are directly adjacent to each other. All exterior faces on the perimeter are considered visible.
For example, the following picture represents a trivial maze with just one (wide) entrance and only four empty reachable spaces:
To whiten this maze you must paint the faces highlighted in yellow above: 16 for its perimeter, plus 8 interior faces. Note that there are faces that are not visible and thus need not be painted.
Definition
Class:
TroytownKeeper
Method:
limeLiters
Parameters:
String[]
Returns:
int
Method signature:
int limeLiters(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.
-
All elements of maze will have the same number of characters.
-
All characters in maze will be either '.' or '#'.
Examples
0)
{"##..#"
,"#.#.#"
,"#.#.#"
,"#####"}
Returns: 24
Example from the problem statement.
1)
{"##",
"##"}
Returns: 8
Only the perimeter of the maze (which has no interior!) has to be painted.
2)
{"######"
,"#....."
,"#.####"
,"#.#..#"
,"#.##.#"
,"#....#"
,"######"}
Returns: 56
3)
{"######"
,"#....."
,"#..#.."
,"#....."
,"######"}
Returns: 36
4)
{"#.#.#.#"
,".#.#.#."
,"#.#.#.#"
,".#.#.#."}
Returns: 36
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.
1 /**
2 * @author Nicky Qu
3 * All Rights Reserved. Oct 21th, 2007
4 */
5 public class TroytownKeeper {
6
7 private int mazeRows,mazeCols,elementsSum,blankSpace,temp;
8 private char[][] charDimensionArray;
9 private int[][] d;
10
11 public int limeLiters(String[] maze) {
12 mazeRows = maze.length;
13 mazeCols = maze[0].length();
14 elementsSum = 2 * (mazeRows + mazeCols);
15 charDimensionArray = new char[mazeRows][mazeCols];
16 d = new int[mazeRows][mazeCols];
17
18 for (int i = 0; i < mazeRows; i++) {
19 charDimensionArray[i] = maze[i].toCharArray();
20 }
21
22 for (int i = 0; i < mazeRows; i++) {
23 for (int j = 0; j < mazeCols; j++) {
24 if (charDimensionArray[i][j] == '.') {
25 blankSpace += 1;
26 }
27 if (charDimensionArray[i][j] == '.' && (i == 0 || i == mazeRows - 1 || j == 0 || j == mazeCols - 1) && d[i][j] == 0) {
28 d[i][j] = 1;
29 elementsSum -= 1;
30 if ((i == 0 && j == 0) || (i == 0 && j == mazeCols - 1) || (i == mazeRows - 1 && j == 0) || (i == mazeRows - 1 && j == mazeCols - 1)) {
31 elementsSum -= 1;
32 }
33 if ((mazeRows - 1 == 0) || (mazeCols - 1 == 0)) {
34 elementsSum -= 1;
35 }
36 }
37 }
38 }
39 for (int l = 0; l < blankSpace; l++) {
40 for (int i = 0; i < mazeRows; i++) {
41 for (int j = 0; j < mazeCols; j++) {
42 if (charDimensionArray[i][j] == '.' && d[i][j] == 1) {
43 temp = i;
44 while (temp > 0 && charDimensionArray[temp - 1][j] == '.' && d[temp - 1][j] == 0) {
45 d[temp - 1][j] = 1;
46 temp--;
47 }
48 temp = i;
49 while (temp < mazeRows - 1 && charDimensionArray[temp + 1][j] == '.' && d[temp + 1][j] == 0) {
50 d[temp + 1][j] = 1;
51 temp++;
52 }
53 temp = j;
54 while (temp > 0 && charDimensionArray[i][temp - 1] == '.' && d[i][temp - 1] == 0) {
55 d[i][temp - 1] = 1;
56 temp--;
57 }
58 temp = j;
59 while (temp < mazeCols - 1 && charDimensionArray[i][temp + 1] == '.' && d[i][temp + 1] == 0) {
60 d[i][temp + 1] = 1;
61 temp++;
62 }
63 }
64 }
65 }
66 }
67
68 for (int i = 0; i < mazeRows; i++) {
69 for (int j = 0; j < mazeCols; j++) {
70 if (d[i][j] == 1) {
71 if (i > 0 && charDimensionArray[i - 1][j] == '#') {
72 elementsSum += 1;
73 }
74 if (i < mazeRows - 1 && charDimensionArray[i + 1][j] == '#') {
75 elementsSum += 1;
76 }
77 if (j > 0 && charDimensionArray[i][j - 1] == '#') {
78 elementsSum += 1;
79 }
80 if (j < mazeCols - 1 && charDimensionArray[i][j + 1] == '#') {
81 elementsSum += 1;
82 }
83 }
84 }
85 }
86
87 return elementsSum;
88 }
89 }
posted on 2007-10-21 21:28
wqwqwqwqwq 閱讀(1465)
評論(1) 編輯 收藏 所屬分類:
Data Structure && Algorithm