959. Regions Cut By Slashes

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 2x2 grid is as follows:Example 2:Input:[ " /”, " “]Output: 1Explanation: The 2x2 grid is as follows:Example 3:Input:[ “/”, “/"]Output: 4Explanation: (Recall that because characters are escaped, “/” refers to /, and “/" refers to /.)The 2x2 grid is as follows:Example 4:Input:[ “/", “/"]Output: 5Explanation: (Recall that because characters are escaped, “/" refers to /, and “/” refers to /.)The 2x2 grid is as follows:Example 5:Input:[ “//”, “/ “]Output: 3Explanation: The 2x2 grid is as follows:Note:1 <= grid.length == grid[0].length <= 30gridi is either ‘/’, ‘’, or ’ ‘.难度：medium题目：给定一个由1X1的方块组成的网格，每个方块由/ ‘ ’（空字符） 3 个元素组成，这些元素将大方块分成若干小的连续区域。求连续区域的个数。思路：将每个小方格用3 Ｘ 3的0、1数组表示。因此题目就转成了0、1矩阵中求0的连续区域个数。/ 转换成001010100 转换成100010001‘ ’ 转换成000000000Runtime: 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); } }}