import org.junit.Test;

import java.util.*;

public class leetcode695 {
    int[] par = new int[100005];
    int[] rak = new int[100005];

    int[] dx = {0,1,0,-1};
    int[] dy = {1,0,-1,0};

    // 并查集的初始化
    public void init(int n) {
        for (int i = 0; i < n; i++) {
            par[i] = i;
            rak[i] = 0;
        }
    }

    // 并查集的根节点查询
    public int find(int x) {
        if (par[x] == x) return x;
        return par[x] = find(par[x]);
    }

    // 并查集的合并
    public void uinte(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (rak[x] < rak[y]) {
            par[x] = y;
        } else {
            par[y] = x;
            if (rak[x] == rak[y]) rak[x]++;
        }
    }

    // 并查集的判断
    public boolean same(int x, int y) {
        return find(x) == find(y);
    }

    public int maxAreaOfIsland(int[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) return 0;

        int row = grid.length;
        int col = grid[0].length;

        init(row*col);

        // 创建连通块
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == 1) {
                    for (int k = 0; k < 4; k++) {
                        int xx = i + dx[k];
                        int yy = j + dy[k];
                        if (isValid(xx, yy, row, col) && grid[xx][yy] == 1 && !same(i*col+j, xx*col+yy)) {
                            uinte(i*col+j, xx*col+yy);
                        }
                    }
                }
            }
        }

        // HashSet保存每个连通块的root
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < row*col; i++) {
            if (par[i] == i && grid[i/col][i%col] == 1) set.add(i);
        }

        // 如果没有岛屿
        if (set.isEmpty()) return 0;

        System.out.println(set);

        // 保存每个连通块的id及其面积
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int root: set) {
            int num = 0;
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    // System.out.println(par[i*col+j]);
                    if (find(i*col+j) == root) num++;
                }
            }
            map.put(root, num);
        }

        // 寻找面积最大的岛屿
        int res = 0;
        for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
            res = Math.max(res, entry.getValue());
        }

        return res;
    }

    // 坐标合法性检验
    public boolean isValid(int x, int y, int row, int col) {
        if (x < 0 || x >= row || y < 0 || y >= col) return false;
        return true;
    }

    @Test
    public void test() {
        int[][] grid = {{1,1,1},
                        {1,1,1},
                        {1,1,1}};
        System.out.println(maxAreaOfIsland_bfs(grid));
    }

}

import org.junit.Test;

import java.util.*;

public class leetcode695 {
    @Test
    public void test() {
        int[][] grid = {{1,1,1},
                        {1,1,1},
                        {1,1,1}};
        System.out.println(maxAreaOfIsland_bfs(grid));
    }

    // 方法二、深度优先搜索
    public int maxAreaOfIsland_dfs(int[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) return 0;

        int row = grid.length;
        int col = grid[0].length;

        int res = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                res = Math.max(res, dfs(grid, i, j));
            }
        }

        return res;
    }

    public int dfs(int[][] grid, int x,int y) {
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == 0) return 0;

        int[] dx = {0,1,0,-1};
        int[] dy = {1,0,-1,0};

        // 记录当前位置的岛屿数量
        int res = grid[x][y];

        // dfs遍历过的地方变为0
        grid[x][y] = 0;

        for (int k = 0; k < 4; k++) {
            int xx = x + dx[k];
            int yy = y + dy[k];
            res += dfs(grid, xx, yy);
        }

        return res;
    }
}

import org.junit.Test;

import java.util.*;

public class leetcode695 {
    // 方法三、广度优先搜索（基于队列实现）
    class coordinate {
        int x;
        int y;

        public coordinate(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public int maxAreaOfIsland_bfs(int[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) return 0;

        int row = grid.length;
        int col = grid[0].length;

        int[] dx = {0,1,0,-1};
        int[] dy = {1,0,-1,0};

        int res = 0;

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {

                if (grid[i][j] == 0) continue;

                int cur = 0;

                Queue<coordinate> que = new LinkedList<>();
                que.offer(new coordinate(i,j));
                cur += grid[i][j];
                grid[i][j] = 0;
                while (!que.isEmpty()) {
                    coordinate pos = que.poll();
                    for (int k = 0; k < 4; k++) {
                        int xx = pos.x + dx[k];
                        int yy = pos.y + dy[k];
                        if (xx < 0 || xx >= row || yy < 0 || yy >= col || grid[xx][yy] == 0) continue;
                        que.offer(new coordinate(xx, yy));
                        cur += grid[xx][yy];
                        grid[xx][yy]=0;
                    }

                }
                res = Math.max(res, cur);
            }
        }

        return res;
    }
}