C++ BFS with illustration of thinking process
Almost all BFS DFS Union-find algorithm are using up-scaled graph to perform searching, my solution follows the same way as well. But I think I would like to sh
Almost all BFS DFS Union-find algorithm are using up-scaled graph to perform searching, my solution follows the same way as well. But I think I would like to share the thinking process of how this idea came up. And this may be too tedious to read if you have already had the idea in mind and just need code example. My code is at the end of the post, using BFS written in C++, and unpolished after the contest.\n\nThink a graph filled with pixels ```\'1\'```, a slash would change some pixels, which form this slash on the graph, with ```\'0\'```. After that, the remained, connected ```\'1\'``` pixels will form some regions, which are what we need to count.\n\nTherefore the problem change to ```How to draw the slash on the pixel graph so that the pixel graph can reflect the divide result?``` To solve this problem, we need to solve those two subproblems: ```How to draw a slash (in a coordinate way on the pixel graph)?``` and ```What is (the size of) the pixel graph?```\n\nThen, we should think from the very beginning. What is the pixel graph of ```grid = [["/"]]``` or ```grid = [["\\\\"]]```? Though there are many valid answers, the smallest valid pixel graph should like this:\n![image](https://assets.leetcode.com/users/acmer29/image_1544990716.png)\n\nWhen ```grid``` become larger, the smallest pixel graph should also become larger as well. For example, if ```grid = [["/", "/"], [" ", "/"]]```, the ```2 * 2``` pixel graph can no longer represent the ```grid```, while ```4 * 4``` can.\n![image](https://assets.leetcode.com/users/acmer29/image_1544991323.png)\n\nAs we can see from the illustration above, ```2 * 2``` cannot reflect the divided region on the upleft side. We need to expand the "resolution" of the pixel graph so that the smallest divided result can be reflect on the graph. \n\nThe above examples give us the idea that actually a slash can be represented by a ```2 * 2``` pixel graph. If those slashes take up ```2 * 2``` elements, then the pixel graph would be ```2n * 2n```, where ```n``` represents to the size of grid. One example is shown as below:\n![image](https://assets.leetcode.com/users/acmer29/image_1544992873.png)\n\n\nAfter the upscale, the problem is transferred to number of islands, either BFS or DFS or Union-find is fine here, except this time one block can go four diagonal directions, since one divided region maybe consist with elements on a diagonal line, which lead to the next problem:\n\n![image](https://assets.leetcode.com/users/acmer29/image_1544992219.png)\n\nFor the pixel graph of ```grid = [["/", "/"], [" ", "/"]]``` above, during searching in eight directions, we need to find a way to make the current element does not consider those diagonal elements blocked by slashes, but if slashes are all represented by ```\'0\'```, there is actually no way to tell which diagonal direction is invalid. \n\nHowever, we know that in the example above, ```graph[1][1]``` cannot go searching upleft and bottomright neighbors since they are blocked by slashes. We then can infer that, backslash should prevent the element searches its upright and bottomleft neighbors. Then it is obvious to represent slash and backslash with different numbers (or characters). Therefore, the final pixel graph looks like the illustration below:\n![image](https://assets.leetcode.com/users/acmer29/image_1544993271.png)\n\nAnd the diagonal searching rules are illustrated as below:\n![image](https://assets.leetcode.com/users/acmer29/image_1544993335.png)\n\nAnd can be described as below:\n```\n(i, j) represents graph[i][j]\nvalid represents (0 <= x && x < n && 0 <= y && y < n)\nif (i - 1, j + 1) is valid and (i - 1, j) == (i, j + 1) == -1, then search (i - 1, j + 1);\nif (i + 1, j + 1) is valid and (i, j + 1) == (i + 1, j) == -2, then search (i + 1, j + 1);\nif (i + 1, j - 1) is valid and (i + 1, j) == (i, j - 1) == -1, then search (i + 1, j - 1);\nif (i - 1, j - 1) is valid and (i, j - 1) == (i - 1, j) == -2, then search (i - 1, j - 1);\n```\n Along with searching ```up```, ```bottom```, ```left```, ```right``` directions, we can finally get the answer.\n \n At last, I have to say I used up almost all remain time (should be 80 min out of 90 min) to come up with this solution and write the code during the contest. I really kneel to those dalao who can realize the essence of this problem and solve it in few minutes. Why we have all undertaken nine-year compulsory education but you are so excellent...\n \n Unpolished Code:\n \n ```C++\n class Solution {\npublic:\n    int regionsBySlashes(vector<string>& grid) {\n        int n = grid.size() * 2;\n        vector<vector<int>> graph(grid.size() * 2, vector<int>(grid.size() * 2, 1));\n        for(int i = 0; i < grid.size(); ++i) {\n            for(int j = 0; j < grid.size(); ++j) {\n                if(grid[i][j] == \'\\\\\') {\n                    graph[i * 2][j * 2] = -1;\n                    graph[i * 2 + 1][j * 2 + 1] = -1;\n                }\n                else if(grid[i][j] == \'/\') {\n                    graph[i * 2][j * 2 + 1] = -2;\n                    graph[i * 2 + 1][j * 2] = -2;\n                }\n            }\n        }\n        int count = 0;\n        int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};\n        for(int i = 0; i < n; ++i) {\n            for(int j = 0; j < n; ++j) {\n                if(graph[i][j] == 1) {\n                    count += 1;\n                    queue<pair<int, int>> que;\n                    que.push({i, j});\n                    graph[i][j] = 0;\n                    while(que.size()) {\n                        auto tmp = que.front();\n                        que.pop();\n                        for(int i = 0; i < 4; ++i) {\n                            int dx = tmp.first + dir[i][0], dy = tmp.second + dir[i][1];\n                            if(isValid(dx, dy, n) && graph[dx][dy] == 1) {\n                                graph[dx][dy] = 0;\n                                que.push({dx, dy});\n                            }\n                        }\n                        int x = tmp.first, y = tmp.second;\n                        if(isValid(x - 1, y - 1, n) && (graph[x - 1][y] == -1 && graph[x][y - 1] == -1) && graph[x - 1][y - 1] == 1) {\n                            graph[x - 1][y - 1] = 0;   \n                            que.push({x - 1, y - 1});\n                        }\n                        if(isValid(x - 1, y + 1, n) && (graph[x - 1][y] == -2 && graph[x][y + 1] == -2) && graph[x - 1][y + 1] == 1) {\n                            graph[x - 1][y + 1] = 0;\n                            que.push({x - 1, y + 1});\n                        }\n                        if(isValid(x + 1, y - 1, n) && (graph[x][y - 1] == -2 && graph[x + 1][y] == -2) && graph[x + 1][y - 1] == 1) {\n                            graph[x + 1][y - 1] = 0;\n                            que.push({x + 1, y - 1});\n                        }\n                        if(isValid(x + 1, y + 1, n) && (graph[x][y + 1] == -1 && graph[x + 1][y] == -1) && graph[x + 1][y + 1] == 1) {\n                            graph[x + 1][y + 1] = 0;\n                            que.push({x + 1, y + 1});\n                        }\n                    }\n                }\n            }\n        }\n        return count;\n    }\nprivate:\n    bool isValid(int x, int y, int n) {\n        return (0 <= x && x < n && 0 <= y && y < n);\n    }\n};\n ```
[]