※ 引述 《JIWP (神楽めあ的钱包)》 之铭言：
:
: 959. Regions Cut By Slashes
:
: 给n*n的grid
:
: 每一格可能包含3种元素'\'、'/'、' '
:
: 请问这个grid里会有几个area
:
思路:
没有
我去看答案
练习union find
看到一个很酷的解法
就是把n*n个格子变成(n+1)*(n+1)个点
最开始每个在外围的点是连在一起的union
然后对每个格子做一些小鸡巴事
什么情况会增加区域？
同一个union的点连在一起的时候
什么时后union合并？
不同union连在一起的时候
做完之后就好了
第一次写unionfind 好丑
```cpp
class Solution {
public:
vector<vector<int>> paper;
int n ;
int regionsBySlashes(vector<string>& grid)
{
n = grid.size();
int count = 1;
paper.resize(n+1,(vector<int>(n+1,0)));
int p = 0;
for(int i = 1 ; i < n ; i ++)
{
for(int j = 1 ; j < n ; j ++)
{
p = i*(n+1)+j;
paper[i][j] =p;
}
}
for(int i = 0 ; i < n ; i ++)
{
for(int j = 0 ; j < n ; j ++)
{
if(grid[i][j] == ' ')continue;
int a ;
int b ;
int c ;
int d ;
if(grid[i][j] == '/')
{
a = i;
b = j+1;
c = i+1;
d = j;
}
else if(grid[i][j] == '\\')
{
a = i;
b = j;
c = i+1;
d = j+1;
}
if(findoin(a,b) == findoin(c,d))
{
count ++;
}
else
{
oin(a,b,c,d);
}
}
}
return count;
}
int findoin(int i , int j)
{
int orig = i*(n+1) + j;
if(paper[i][j] != orig)
{
paper[i][j] = findoin( paper[i][j]/(n+1) , paper[i][j]%(n+1) );
}
return paper[i][j];
}
void oin(int a , int b , int c , int d )
{
int ai = paper[a][b]/(n+1);
int bi = paper[a][b]%(n+1);
int ci = paper[c][d]/(n+1);
int di = paper[c][d]%(n+1);
if(ai*(n+1)+bi < ci*(n+1)+di)paper[ci][di] = ai*(n+1)+bi;
else paper[ai][bi] = ci*(n+1)+di;
}
};
```