# 959. Regions Cut By Slashes (in the end use 200)

This question is quite hard to find the idea -> 2\*2 to 6\*6 grid...

T: O(n^2), n is 3m (m is 2)

```java
class Solution {
    private static final int[][] DIRECTIONS = {{0,1}, {1, 0}, {0,-1}, {-1, 0}};
    public int regionsBySlashes(String[] grid) {
        char[][] originGrid = new char[grid.length][grid[0].length()]; // 2, 2
        int row = grid.length*3;
        int col = grid[0].length()*3;
        int[][] newGrid = new int[row][col];

        for (int i = 0; i < grid.length; i++) {
            String s = grid[i];
            for (int j = 0; j < s.length(); j++) {
                originGrid[i][j] = s.charAt(j);
            }
        }
        for (int i = 0; i < originGrid.length; i++) {
            for (int j = 0; j < originGrid.length; j++) {
                if (originGrid[i][j] == '/') {
                    newGrid[3*i][3*j+2] = 1;
                    newGrid[3*i+1][3*j+1] = 1;
                    newGrid[3*i+2][3*j] = 1;
                } else if (originGrid[i][j] == '\\') {
                    newGrid[3*i][j*3] = 1;
                    newGrid[3*i+1][j*3+1] = 1;
                    newGrid[3*i+2][j*3+2] = 1;
                }
            }
        }

        int regionCount = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (newGrid[i][j] == 0) {
                    dfs(newGrid, i, j);
                    regionCount++;
                }
            }
        }
        return regionCount;
    }
    
    private void dfs(int[][] newGrid, int i, int j) {
        int m = newGrid.length;
        int n = newGrid[0].length;
        if (i < 0 || i >= m || j < 0 || j >= n || newGrid[i][j] == 1) {
            return;
        }
        newGrid[i][j] = 1;
        for (int[] dir : DIRECTIONS) {
            dfs(newGrid, i+dir[0], j+dir[1]);
        }
    }
}

/**

0010
0100


0110
1001
1001
0110


0001
0010
0000
0000

seems convert to 2*2 can solve this question,...
but!
2*2 will fail in this case


["//", "//"]
ans is 4

0101
1010 because 4 direction can connect .,,
0101
1010

how about use diagnal direction, no because  left top to right buttom will be connected as well.

so need to to use 3*3

012345

001001. 0
010010. 1
100100. 2
001001  3
010010. 4
100100. 5


/ -> (0,0) in orignal array -> 0*3, 0*3+2). (0*3+1, 0+1), (0*3+1, 0)
/ -> (0,1) in orignal array -> 0*3, 1*3+2). (0*3+1, 1*3+1), (0*3+1, 1*3+0)

/ -> row*3, col*3 +2, 
   row*3+1, col*3 +1, 
   row*3+2, col*3+0

\ -> row*3, col*3, 
     row*3+1, col*3 +1, 
     row*3+2, col*3 +2


if (originGrid[i][j] == '/') {
                    newGrid[3*i][3*j+2] = 1;
                    newGrid[3*i+1][3*j+1] = 1;
                    newGrid[3*i+2][3*j] = 1;
                } else if (originGrid[i][j] == '\\') {
                    newGrid[3*i][j*3] = 1;
                    newGrid[3*i+1][j*3+1] = 1;
                    newGrid[3*i+2][j*3+2] = 1;
                }
 */
```
