Python Solution with explanation (Build the beach of the Island)
The main idea is to build a beach for each island.... First counter the area of each Island and save it in the "count". Then find all boundary cells (with the b
The main idea is to build a beach for each island.... First counter the area of each Island and save it in the "count". Then find all boundary cells (with the boundary I mean the ocean not the land) of a certain island which are called beach. If two islands can be connected to each other with changing only one cell from "0" to "1", the beaches of these two islands must overlap at this cell. So for each island, find all the beach cell and add the value with the area of the island. For example, given the grid [[0,1,0,1,1,0]]. There are two island with area [1,2], the beach of the first island is the first and the third cell, the beach of the second island is the third and sixth cell. After calculating the beach, we get [[1,0,3,0,0,2]], and the result is 3+1.\n\n\n        import copy\n        res = []\n        for i in grid:\n            res += i\n        if 0 not in res:\n            return len(res)\n        m , n = len(grid) , len(grid[0])\n\n        g = [[0]*(n+2)] + [[0] + i + [0] for i in grid] + [[0]*(n+2)]\n\n        res = copy.deepcopy(g)\n        check = copy.deepcopy(g) # to check\n        def countArea(i,j):\n            if g[i][j] == 0 or i<0 or i == m+2 or j < 0 or j == n+2:\n                return 0\n            g[i][j] = 0\n            return 1+sum(list(map(countArea,[i,i,i+1,i-1],[j+1,j-1,j,j])))\n\n        count = []\n        for x in range(1,m+1):\n            for y in range(1,n+1):\n                if g[x][y] == 1:\n                    count += countArea(x,y),\n\n        g = copy.deepcopy(res)\n        def beach(i,j,num):\n            if g[i][j] == 0 or i<0 or i == m+2 or j < 0 or j == n+2:\n                res[i][j] += num\n                g[i][j] = "X"\n                return\n            if g[i][j] == "X":\n                return\n            g[i][j] = "X"\n            list(map(beach,[i,i,i-1,i+1],[j-1,j+1,j,j],[num]*4))\n            return\n        for x in range(1,m+1):\n            for y in range(1,n+1):\n                if g[x][y] == 1:\n                    beach(x,y,count.pop(0))\n                    for a in range(1,m+1):\n                        for b in range(1,n+1):\n                            g[a][b] = [g[a][b],0][g[a][b] == "X"]\n\n        Res = []\n        for i in res:\n            Res += i\n\n        return max(Res)+1\n\n
[]