尝试使用markdown，记一次并查集解题记录……

题目

在由 1 x 1 方格组成的 N x N 网格?grid 中，每个 1 x 1?方块由 /、\ 或空格构成。这些字符会将方块划分为一些共边的区域。
（请注意，反斜杠字符是转义的，因此 \ 用 "\"?表示。）。
返回区域的数目。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/regions-cut-by-slashes

输入输出实例

思路

并查集。知道了使用并查集来做这个题，那怎么将思路转换为代码呢?

1. 首先，在每一个方格中画一个X,将方格划分为上右下左四个方块。如下图所示：
   
2. 斜率大于0的斜杠就将区域0、3合并，区域1、2合并。
3. 斜率小于0的斜杠就将区域0、1合并，区域2、3合并。
4. 空格就将区域0、1、2、3合并。
5. 将一个方块中的区域合并完之后，再将相邻方块的区域进行合并。如下图所示，被红圈圈在一起的区域应该被合并：
   
6. 处理完这些之后就可以查找有几个区域了。

每个方格被划分为了4个子区域，对这些子区域进行编号，压缩为一维数组（如上图中所示），然后进行并查集的处理操作。详细可见代码。

  public class Main {
public int regionsBySlashes(String[] grid) {
	int N = grid.length;
    Region reg = new Region(4*N*N);
    
    //System.out.println("N: "+N);
    for(int r=0; r<N; r++) {
    	for(int c=0; c<N; c++){
    		int idx = r * N * 4 + c * 4;
    		if(grid[r].charAt(c) == ‘/‘){
    			reg.union(idx+0, idx+3);//0 3
    			reg.union(idx+1, idx+2);//1 2
    		}
    		if(grid[r].charAt(c) == ‘\\‘) {
    			reg.union(idx+0, idx+1);//0 1
    			reg.union(idx+2, idx+3);//2 3
    		}
    		if(grid[r].charAt(c) == ‘ ‘) {
    			//0 1 2 3 合并
    			reg.union(idx+0, idx+1);
    			reg.union(idx+2, idx+3);
    			reg.union(idx+0, idx+2);
    		}
    		
    		//System.out.println("idx: "+idx);
    		//合并不同方格中的区域
    		if(r-1 >= 0) {
    			//System.out.println("r-1: " + (idx+0)+" : "+(idx + 0 - N * 4 + 2));
    			//与上方区域合并
    			reg.union(idx+0, idx + 0 - N * 4 + 2);
    		}
    		if(r+1 < N) {
    			//与下方区域合并
    			reg.union(idx+2, idx + 2 + N * 4 - 2);
    		}
    		if(c-1 >= 0) {
    			//与左方区域合并
    			reg.union(idx+3, idx + 3 - 6);
    		}
    		if(c+1 < N) {
    			//与右方区域合并
    			reg.union(idx+1, idx + 1 + 6);
    		}
    	}
    }
    return reg.countRegion();
}


public static void main(String[] args) {
	// TODO Auto-generated method stub
	String[] grid = new String[3];
	grid[0] = " /\\";
	grid[1] = " \\/";
	grid[2] = "\\  ";
	Main mm = new Main();
	System.out.println(mm.regionsBySlashes(grid));
}
  }


  class Region{
public int[] map;
public int N;

public int countRegion() {
	int ans = 0;
	for(int i=0; i<N; i++) {
		if(map[i]==i) {
			ans++;
		}
	}
	return ans;
}

public Region(int N) {
	this.N = N;
	map = new int[N+5];
	for(int i=0; i<N+5; i++) {
		map[i] = i;
	}
}
	
public int find(int x) {
	//System.out.println(x);
	if( map[x] == x) {
		return x;
	}else {
		map[x] = find(map[x]);
		return map[x];
	} 
}

public void union(int x,int y) {
	int tx = find(x);
	int ty = find(y);
	
	if(ty != tx) {
		map[ty] = map[tx];
	}
}
  }

最后吐槽一下，除了代码这一块，别的地方用markdown写要比TinyMCE舒服多了，就是这个代码排版很令人捉急（也可能是我第一次用markdown的原因……）

LeetCode959 由斜杠划分区域（Java并查集）

原文：https://www.cnblogs.com/sykline/p/13206448.html