共计 1900 个字符，预计需要花费 5 分钟才能阅读完成。
In a N x N grid composed of 1 x 1 squares, each 1 x 1 square consists of a /, , or blank space. These characters divide the square into contiguous regions.
(Note that backslash characters are escaped, so a is represented as “\”.)
Return the number of regions.
Example 1:
Input:[” /”, “/ “]Output: 2Explanation: The 2×2 grid is as follows:
Example 2:
Input:[” /”, ” “]Output: 1Explanation: The 2×2 grid is as follows:
Example 3:
Input:[“\/”, “/\”]Output: 4Explanation: (Recall that because characters are escaped, “\/” refers to /, and “/\” refers to /.)The 2×2 grid is as follows:
Example 4:
Input:[“/\”, “\/”]Output: 5Explanation: (Recall that because characters are escaped, “/\” refers to /, and “\/” refers to /.)The 2×2 grid is as follows:
Example 5:
Input:[“//”, “/ “]Output: 3Explanation: The 2×2 grid is as follows:
Note:
1 <= grid.length == grid[0].length <= 30gridi is either ‘/’, ”, or ‘ ‘.
难度：medium
题目：给定一个由 1X1 的方块组成的网格，每个方块由 /‘’（空字符）3 个元素组成，这些元素将大方块分成若干小的连续区域。求连续区域的个数。
思路：将每个小方格用 3 X 3 的 0、1 数组表示。因此题目就转成了 0、1 矩阵中求 0 的连续区域个数。/ 转换成 001010100 转换成 100010001‘’转换成 000000000
Runtime: 12 ms, faster than 85.37% of Java online submissions for Regions Cut By Slashes.
class Solution {
/**
* 001
* / -> 010
* 100
*
* 100
* \ -> 010
* 001
*
* 000
* ‘ ‘->000
* 000
*
* convert to find the isolated 0s by 1
*/
public int regionsBySlashes(String[] grid) {
int row = grid.length;
int trippleRow = 3 * row;
int[][] iGrid = new int[trippleRow][trippleRow];
for (int i = 0; i < trippleRow; i += 3) {
char[] sc = grid[i / 3].toCharArray();
for (int j = 0; j < trippleRow; j += 3) {
char c = sc[j / 3];
if (‘/’ == c) {
iGrid[i][j + 2] = iGrid[i + 1][j + 1] = iGrid[i + 2][j] = 1;
} else if (‘\\’ == c) {
iGrid[i][j] = iGrid[i + 1][j + 1] = iGrid[i + 2][j + 2] = 1;
}
}
}
int count = 0;
for (int i = 0; i < trippleRow; i++) {
for (int j = 0; j < trippleRow; j++) {
if (0 == iGrid[i][j]) {
colorGrid(iGrid, i, j);
count++;
}
}
}
return count;
}
private void colorGrid(int[][] grid, int i, int j) {
grid[i][j] = 1;
// up
if (0 == grid[Math.max(i – 1, 0)][j]) {
colorGrid(grid, i – 1, j);
}
// down
if (0 == grid[Math.min(i + 1, grid.length – 1)][j]) {
colorGrid(grid, i + 1, j);
}
// left
if (0 == grid[i][Math.max(j – 1, 0)]) {
colorGrid(grid, i, j – 1);
}
// right
if (0 == grid[i][Math.min(j + 1, grid[0].length – 1)] ) {
colorGrid(grid, i, j + 1);
}
}
}
