public class Solution { public int NumIslands(char[][] grid) { if(grid == null || grid.Count() == 0) return 0; int rowCount = grid.Count(); int colCount = grid[0].Count(); int waters = 0; UnionFind uf = new UnionFind(grid); for(int i=0;i<rowCount;i++) { for(int j=0;j<colCount;j++) { if(grid[i][j] == '0') { waters++; }else{ int[][] direction = new int[][]{ new int[]{0,1}, new int[]{0,-1}, new int[]{1,0}, new int[]{-1,0} }; foreach(var dir in direction) { int x = i + dir[0]; int y = j + dir[1]; if(x >= 0 && y >= 0 && x < rowCount && y < colCount && grid[x][y] == '1') { uf.Union(x*colCount+y,i*colCount+j); } } } } } return uf.GetCount() - waters; } } // unionFind函数 public class UnionFind{ private int[] root = null; private int count = 0; public UnionFind(char[][] grid) { int colCount = grid.Length; int rowCount = grid[0].Length; root = new int[colCount*rowCount]; count = colCount*rowCount; for (int i = 0; i < colCount*rowCount; i++) { root[i] = i; } } private int Find(int x) { if (x == root[x]) { return x; } return root[x] = Find(root[x]); } public void Union(int x,int y) { int rootX = Find(x); int rootY = Find(y); if (rootX != rootY) { root[rootX] = rootY; count --; } } public int GetCount(){ return count; } }
标签:200,int,查集,rowCount,算法,colCount,grid,root,public From: https://www.cnblogs.com/Insist-Y/p/17320864.html