Readme

959.Regions-Cut-By-Slashes

解法1：将每个格子倍增9倍

此题非常巧妙。我们将每一个格子都再细化为3*3的像素，那么“\”和“/”就各自变成了一条斜对角线。于是我们再看这个细化之后的3N*3N的矩阵，就会惊奇地发现，题目中定义的Regions此时都变成是像素联通的了。这就转换成了number of islands的题，用DFS,BFS或者Union Find都可以很轻松地解决。

解法2：Union Find

有一个更高效和巧妙的解法，不需要拆分格子。我们不考虑每个cell，而是考虑每个网点（即经纬线的相交点）。这样的网点有(N+1)*(N+1)个。最初始的时候我们将所有外围的点聚为一类，即满足i==0||i==N||j==0||j==N的网点聚在一起。其他内陆的网点都自成一类。

然后我们逐个考察cell。如果这个cell包含了斜线，那么会将两个网点a和b相连接（左上和右下，或者左下和右上）。此时如果a和b两点属于不同的类，那么意味着这个斜线不会生成一个新的封闭空间！但是记得我们需要紧接着将a和b聚类在一起。相反，如果a和b两点已经聚属于同一类，那么意味着这个斜线一定会生成一个新的封闭空间！这个时候计数器就要加1.

我们考察完每个cell和所包含斜线的影响，最终返回计数器的值即可。注意，计数器的初始值应该是1.

Leetcode Link