p*****p
发帖数: 379 | 7 刚写了个，上个部分代码
private enum Direction {LEFT, RIGHT, UP, DOWN};
private static float getCurrentPathMax(int currentRow, int currentCol, int[]
[] maze, int[][] visited, Direction lastStep) {
int rows = maze.length, cols = maze[0].length;
if (currentRow < 0 || currentRow >= rows || currentCol < 0 || currentCol
>= cols) {
return -1;
}
if (maze[currentRow][currentCol] == 0) {
// blank
if (visited[currentRow][currentCol] == 3) {
return 0;
}
visited[currentRow][currentCol] = 3;
float nextPathArea = getCurrentPathMax(currentRow - 1, currentCol,
maze, visited, Direction.UP);
if (nextPathArea == -1) {
return -1;
}
else {
return 1 + nextPathArea;
}
}
else if (maze[currentRow][currentCol] == 1) {
// slash wall
float nextPathArea = 0;
switch (lastStep) {
case UP:
if ((visited[currentRow][currentCol] & 2) != 0) {
return 0;
}
visited[currentRow][currentCol] |= 2;
nextPathArea = getCurrentPathMax(currentRow, currentCol + 1,
maze, visited, Direction.RIGHT);
break;
case DOWN:
if ((visited[currentRow][currentCol] & 1) != 0) {
return 0;
}
visited[currentRow][currentCol] |= 1;
nextPathArea = getCurrentPathMax(currentRow, currentCol - 1,
maze, visited, Direction.LEFT);
break;
case LEFT:
if ((visited[currentRow][currentCol] & 2) != 0) {
return 0;
}
visited[currentRow][currentCol] |= 2;
nextPathArea = getCurrentPathMax(currentRow + 1, currentCol,
maze, visited, Direction.DOWN);
break;
case RIGHT:
if ((visited[currentRow][currentCol] & 1) != 0) {
return 0;
}
visited[currentRow][currentCol] |= 1;
nextPathArea = getCurrentPathMax(currentRow - 1, currentCol,
maze, visited, Direction.UP);
break;
}
if (nextPathArea == -1) {
return -1;
}
else {
return 0.5f + nextPathArea;
}
}
else {
// backslash wall
float nextPathArea = 0;
switch (lastStep) {
case UP:
if ((visited[currentRow][currentCol] & 2) != 0) {
return 0;
}
visited[currentRow][currentCol] |= 2;
nextPathArea = getCurrentPathMax(currentRow, currentCol - 1,
maze, visited, Direction.LEFT);
break;
case DOWN:
if ((visited[currentRow][currentCol] & 1) != 0) {
return 0;
}
visited[currentRow][currentCol] |= 1;
nextPathArea = getCurrentPathMax(currentRow, currentCol + 1,
maze, visited, Direction.RIGHT);
break;
case LEFT:
if ((visited[currentRow][currentCol] & 1) != 0) {
return 0;
}
visited[currentRow][currentCol] |= 1;
nextPathArea = getCurrentPathMax(currentRow - 1, currentCol,
maze, visited, Direction.UP);
break;
case RIGHT:
if ((visited[currentRow][currentCol] & 2) != 0) {
return 0;
}
visited[currentRow][currentCol] |= 2;
nextPathArea = getCurrentPathMax(currentRow + 1, currentCol,
maze, visited, Direction.DOWN);
break;
}
if (nextPathArea == -1) {
return -1;
}
else {
return 0.5f + nextPathArea;
}
}
}
public static float getMaxArea(int[][] maze) {
int rows = maze.length, cols = maze[0].length;
int[][] visited = new int[rows][cols];
// 0 - not visited
// 1 - upper half visited
// 2 - lower half visited
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
visited[i][j] = 0;
}
}
float max = 0;
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
if (visited[i][j] == 3) {
continue;
}
if (maze[i][j] == 0) {
continue;
}
else {
if ((visited[i][j] & 1) == 0) {
visited[i][j] |= 1;
max = Math.max(max, 0.5f + getCurrentPathMax(i - 1, j,
maze, visited, Direction.UP));
}
if ((visited[i][j] & 2) == 0) {
visited[i][j] |= 2;
max = Math.max(max, 0.5f + getCurrentPathMax(i + 1, j,
maze, visited, Direction.DOWN));
}
}
}
}
return max;
} |
