Simple java DFS solution with explanation
Simple java solution.\n\nRuntime: 7 ms, faster than 43.00% of Java online submissions for Regions Cut By Slashes.\nMemory Usage: 38.5 MB, less than 41.24% of Ja
Simple java solution.\n\nRuntime: 7 ms, faster than 43.00% of Java online submissions for Regions Cut By Slashes.\nMemory Usage: 38.5 MB, less than 41.24% of Java online submissions for Regions Cut By Slashes.\n\nYou need to create an array that is 3 times larger than the input.\nIt turns out that for one cell from the input array, we create 9 cells.\nExample: \n\n1) grid = { "/" }\narr = {\n001,\n010,\n101};\n\n2) grid = { "\\\\" }\narr = {\n100,\n010,\n001};\n\nThen we find the cell with the value 0, and start the depth-first search and change the value everywhere from 0 to 1. After each launch of the depth-first search method, need increment the answer. Then we return the received answer.\n\ndfs solution:\n\n    class Solution {\n\n      public int regionsBySlashes(String[] grid) {\n        int[][] arr = new int[grid.length * 3][grid.length * 3];\n\n        for (int i = 0; i < grid.length; i++) {\n          for (int j = 0; j < grid[i].toCharArray().length; j++) {\n            if (grid[i].charAt(j) == \'/\') {\n              arr[i * 3][j * 3 + 2] = 1;\n              arr[i * 3 + 1][j * 3 + 1] = 1;\n              arr[i * 3 + 2][j * 3] = 1;\n            } else if (grid[i].charAt(j) == \'\\\\\') {\n              arr[i * 3][j * 3] = 1;\n              arr[i * 3 + 1][j * 3 + 1] = 1;\n              arr[i * 3 + 2][j * 3 + 2] = 1;\n            }\n          }\n        }\n\n        int regions = 0;\n        for (int i = 0; i < arr.length; i++) {\n          for (int j = 0; j < arr[i].length; j++) {\n            if (arr[i][j] == 0) {\n              dfs(i, j, arr);\n              regions++;\n            }\n          }\n        }\n\n        return regions;\n      }\n\n      private void dfs(int i, int j, int[][] arr) {\n        if (i < 0 || i >= arr.length || j < 0 || j >= arr.length || arr[i][j] == 1) return;\n        arr[i][j] = 1;\n        dfs(i - 1, j, arr);\n        dfs(i + 1, j, arr);\n        dfs(i, j - 1, arr);\n        dfs(i, j + 1, arr);\n      }\n\n    }
['Depth-First Search', 'Java']