# 1559. Detect Cycles in 2D Grid
###### tags: `Leetcode` `Medium` `FaceBook` `Union Find`
Link: https://leetcode.com/problems/detect-cycles-in-2d-grid/
## 思路 $O(mn*c)$ $O(mn)$
### Union Find $O(mn*c)$ $O(mn)$
如果发现一条边的两个点的father是同一个的话，就说明成环了
由于grid是二维存的，而并查集是一维的，因此要做个转换

这题用union find效果会比较好，虽然复杂度都是一样的
### BFS $O(M^2N^2)$ $O(MN)$
从任意一点开始，对同一个value的所有像素做常规的遍历。如果遍历的过程中遇到了之前访问过的格子，那么就是有环。注意遍历的过程中不能走“回头路”，即从A遍历到B，那么从B开始的遍历就不能包括A。
我们记录每个点是通过走哪个方向从它的上一个点来的，那么从这个点出发往外走的时候就不能走相反方向
### DFS
DFS
但是要注意的一点是由于要找circle，所以一旦回到被visit过的点的时候就返回true（说明有circle），这就导致我们不能在访问一个点，并且找它的邻居的时候把它来的时候经过的那个点又加进来，这样无论如何都会有circle
例如： a-a 先访问左边的a，再访问右边的a，在访问右边的a的时候，不能回去再找到左边的a了，因此要记录来时经过的那个node
一开始的思路是在跑while回圈的时候用prev记录上一个经过的点，那么curr在找neighbor的时候不能找和prev一模一样的点，但是后来发现由于是用dfs，所以上一个访问的点不一定是curr的neighbor，因此要用递归做

## Code
### Union Find

class Solution {
    private int[] fa;
    private int[] size;
    public boolean containsCycle(char[][] grid) {
        int r = grid.length;
        int c = grid[0].length;
        
        fa = new int[r*c];
        size = new int[r*c];
        
        for(int i = 0;i < r;i++){
            for(int j = 0;j < c;j++){
                fa[i*c+j] = i*c+j;
                size[i*c+j] = 1;
            }
        }
        
        for(int i = 0;i < r;i++){
            for(int j = 0;j < c;j++){
                if(i+1<r && grid[i][j] == grid[i+1][j]){
                    if(combine(i*c+j, (i+1)*c+j)) return true;
                }
                if(j+1<c && grid[i][j] == grid[i][j+1]){
                    if(combine(i*c+j, i*c+j+1)) return true;
                }
            }
        }
        return false;
    }
    public int find(int a){
        if(a == fa[a]) return a;
        else return fa[a] = find(fa[a]);
    }
    public boolean combine(int a, int b){
        a = find(a);
        b = find(b);
        if(a==b) return true;
        if(size[a]>size[b]){
            fa[b] = a;
            size[a] += size[b];
        }
        else{
            fa[a] = b;
            size[b] += size[a];
        }
        return false;
    }
}

### BFS

class Solution {
    public boolean containsCycle(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
        boolean[][] visited = new boolean[m][n];
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(visited[i][j]) continue;
                
                Queue<int[]> q = new LinkedList<>();
                q.add(new int[]{i,j,-1});
                while(!q.isEmpty()){
                    int[] curr = q.poll();
                    for(int k=0; k<dirs.length; k++){
                        int[] dir = dirs[k];
                        int newx = curr[0]+dir[0];
                        int newy = curr[1]+dir[1];
                        if(k==0 && curr[2]==1) continue;
                        if(k==1 && curr[2]==0) continue;
                        if(k==2 && curr[2]==3) continue;
                        if(k==3 && curr[2]==2) continue;
                        if(newx>=0 && newy>=0 && newx<m && newy<n && grid[newx][newy]==grid[i][j]){
                            if(visited[newx][newy]) return true;
                            visited[newx][newy] = true;
                            q.add(new int[]{newx, newy, k});
                        }
                    }
                }
            }
        }
        return false;
    }
}

### DFS

class Solution {
    int[][] directions = new int[][]{{-1,0},{1,0},{0,1},{0,-1}};
    public boolean containsCycle(char[][] grid) {
        int r = grid.length;
        int c = grid[0].length;
        boolean[][] visited = new boolean[r][c];
        for(int i = 0;i < r;i++){
            for(int j = 0;j < c;j++){
                if(!visited[i][j]){
                    if(dfs(grid[i][j], new int[]{i, j}, new int[]{-1, -1}, visited, grid, r, c)) return true;
                }
            }
        }
        return false;
    }
    private boolean dfs(char startChar, int[] curr, int[] prev, boolean[][] visited, char[][] grid, int r, int c){
        visited[curr[0]][curr[1]] = true;
        List<int[]> nextPos = getNext(curr, r, c);
        for(int[] next:nextPos){
            if(!(next[0]==prev[0] && next[1]==prev[1])){
                if(grid[next[0]][next[1]]==startChar){
                    if(visited[next[0]][next[1]]){
                        return true;
                    }
                    else{
                        visited[next[0]][next[1]] = true;
                        if(dfs(startChar, next, curr, visited, grid, r, c)) return true;
                    }
                }
            }
        }
        return false;
    }
    private List<int[]> getNext(int[] curr, int r, int c){
        List<int[]> ans = new ArrayList<>();
        for(int i = 0;i < directions.length;i++){
            int newi = curr[0]+directions[i][0];
            int newj = curr[1]+directions[i][1];
            if(newi>=0 && newi<r && newj>=0 && newj<c){
                ans.add(new int[]{newi, newj});
            }
        }
        return ans;
    }
}