Given a non-empty 2D array grid of 0's and 1's, an island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

Example 1:

 [0,0,1,0,0,0,0,1,0,0,0,0,0],

 [0,0,0,0,0,0,0,1,1,1,0,0,0],

 [0,1,1,0,1,0,0,0,0,0,0,0,0],

 [0,1,0,0,1,1,0,0,1,0,1,0,0],

 [0,1,0,0,1,1,0,0,1,1,1,0,0],

 [0,0,0,0,0,0,0,0,0,0,1,0,0],

 [0,0,0,0,0,0,0,1,1,1,0,0,0],

 [0,0,0,0,0,0,0,1,1,0,0,0,0]]

Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.

Example 2:

[[0,0,0,0,0,0,0,0]]

Given the above grid, return 0.

function testIsland()

clc

clear all

close all

% data = [[0,0,1,0,0,0,0,1,0,0,0,0,0],

%          [0,0,0,0,0,0,0,1,1,1,0,0,0],

%          [0,1,1,0,1,0,0,0,0,0,0,0,0],

%          [0,1,0,0,1,1,0,0,1,0,1,0,0],

%          [0,1,0,0,1,1,0,0,1,1,1,0,0],

%          [0,0,0,0,0,0,0,0,0,0,1,0,0],

%          [0,0,0,0,0,0,0,1,1,1,0,0,0],

%          [0,0,0,0,0,0,0,1,1,0,0,0,0]];

data = [[0,0,0,0,0,0,0,0]];

[island_num, ~] = island(data);

end

function [island_num, label] = island(data)

island_num = 0;

label = data;

for i=1:size(label, 1)

    for j=1:size(label, 2)

        if label(i, j)==1

            island_num = island_num +1;

            label = recurseFinding(label, i, j, island_num);

        end

    end

end

end

function data = recurseFinding(data, i, j, island_num)

if i>0 && i<=size(data, 1) && j>0 && j<=size(data, 2) && data(i, j)==1

    data(i, j) = island_num;

    data = recurseFinding(data, i-1, j, island_num);

    data = recurseFinding(data, i+1, j, island_num);

    data = recurseFinding(data, i, j-1, island_num);

    data = recurseFinding(data, i, j+1, island_num);

end

end

 import numpy as np

 import copy

 def recurseFinding(dict_in, key, islands):

     ret_list = []

     for val in dict_in[key]:

         ret_list.append(val)

         if dict_in.__contains__(val) and  not islands.__contains__(val):

             ret_list = list(set(ret_list + [l for l in recurseFinding(dict_in, val, islands)]))

     return ret_list

 def island_num(data):

     loc_xy = [[i, j] for i in range(data.shape[0]) for j in range(data.shape[1]) if data[i,j]>0]  # 得到不为0的所有坐标(x,y)

     loc_idx_dict = {i:loc_xy[i] for i in range(len(loc_xy))}  # 给坐标编号，方便后面使用

     loc_key = sorted(set(loc_idx_dict.keys()))

     pairs_dict = {}

     for i in range(len(loc_key)-1):

         for j in range(i+1, len(loc_key)):

             if abs(loc_idx_dict[loc_key[i]][0] - loc_idx_dict[loc_key[j]][0]) + abs(loc_idx_dict[loc_key[i]][1] - loc_idx_dict[loc_key[j]][1]) == 1:

                 if not pairs_dict.__contains__(loc_key[i]):

                     pairs_dict[loc_key[i]] = []

                 pairs_dict[loc_key[i]].append(loc_key[j])

     islands_dict = {}

     for k, v in pairs_dict.items():

         if k in [j for i in islands_dict.values() for j in i]:

             continue

         if not islands_dict.__contains__(k):

             islands_dict[k] = copy.deepcopy(pairs_dict[k])

         islands_dict[k] = recurseFinding(pairs_dict, k, islands_dict)

     ############### method1

     # islands_keys = sorted(set(islands_dict.keys()))  # 可能出现11:[18,19], 12:[18]的情况，需要将12合并到11中，继续遍历一下，此处比较麻烦

     # for i in range(len(islands_keys)-1):

     #     for j in range(i+1, len(islands_keys)):

     #         flags= False

     #         for v2 in islands_dict[islands_keys[j]]:

     #             if v2 in islands_dict[islands_keys[i]]:

     #                 islands_dict[islands_keys[i]].append(islands_keys[j])

     #                 flags = True

     #         if flags:

     #             islands_dict[islands_keys[j]] = []  # 此处无法删除12的key，否则程序崩溃，因而只能置空，后面删除

     ############### method1 end

     ############### method2

     reverse_pairs = {}  # 得到反转的对应关系，如果出现11:[18,19], 12:[18]的情况，则反转后的键18对应2个值

     for k,v in islands_dict.items():

         for v0 in v:

             if not reverse_pairs.__contains__(v0):

                 reverse_pairs[v0] = []

             reverse_pairs[v0].append(k)

     delete_key = []   # 理论上比method1计算量少，但是不确定是否完全正确。。。

     for k,v in reverse_pairs.items():

         if len(v) > 1:

             for i in range(1, len(v)):

                 if v[i] not in islands_dict[v[0]]:

                     islands_dict[v[0]].append(v[i])

                 if v[i] not in delete_key:

                     delete_key.append(v[i])

     for k in delete_key:    # 删除对应的key

         del islands_dict[k]

     ############### method2 end

     islands_dict = {k:set(v) for k, v in islands_dict.items() if len(v) > 0}

     pairs_keys = set(pairs_dict.keys())

     pairs_vals = set([v0 for v in pairs_dict.values() for v0 in v])

     alone_loc = set(loc_key) - (pairs_keys | pairs_vals) #由于优先级，后面需要加括号

     islands_dict.update({i:[] for i in alone_loc})   # 将单独的位置合并到islands_dict中

     return len(islands_dict)   # 通过islands_dict及loc_idx_dict可以找到对应的坐标，此处省略

 # data=np.array([  [0,0,1,0,0,0,0,1,0,0,0,0,0],

                  # [0,0,0,0,0,0,0,1,1,1,0,0,0],

                  # [0,1,1,0,1,0,0,0,0,0,0,0,0],

                  # [0,1,0,0,1,1,0,0,1,0,1,0,0],

                  # [0,1,0,0,1,1,0,0,1,1,1,0,0],

                  # [0,0,0,0,0,0,0,0,0,0,1,0,0],

                  # [0,0,0,0,0,0,0,1,1,1,0,0,0],

                  # [0,0,0,0,0,0,0,1,1,0,0,0,0]])

 data=np.array([[0,0,0,0,0,0,0,0]])

 num = island_num(data)

 print(num)