1162. Map analysis - non recursive method

1162. Map analysis

Now you have a copy of n x n Of grid grid, Each of the above Cell Use both 0 and 1 It's marked . among 0 On behalf of the ocean ,1 Representing land .

Please find an ocean cell , The ocean cell has the largest distance to the nearest land cell , And return the distance . If there's only land or ocean on the grid , Please return -1.

The distance we're talking about here is 「 Manhattan distance 」（ Manhattan Distance）：(x0, y0) and (x1, y1) The distance between these two cells is |x0 - x1| + |y0 - y1| .

Example 1：

Input ：grid = [[1,0,1],[0,0,0],[1,0,1]]
Output ：2
explain ：
Ocean cell (1, 1) And the distance between all the land cells reaches the maximum , The maximum distance is 2.

Example 2：

Input ：grid = [[1,0,0],[0,0,0],[0,0,0]]
Output ：4
explain ：
Ocean cell (2, 2) And the distance between all the land cells reaches the maximum , The maximum distance is 4.

For this question , If we don't use recursive methods , Then use two arrays to store 0 and 1 Coordinates of , Then calculate , It can reduce the computational cost , But this way , Not yet optimal , It can be further judged that the calculation stops , The solution code is as follows ：

int maxDistance(int** grid, int gridSize, int* gridColSize){
    
    int n=gridSize,m=gridColSize[0];
    int store0[n*m][2];
    int store1[n*m][2];
    int i,j;
    int size0=0,size1=0;
    for(i=0;i<n;i++){
    
        for(j=0;j<m;j++){
    
            if(grid[i][j]==0){
    
                store0[size0][0]=i;
                store0[size0][1]=j;
                size0++;
            }
            else{
    
                 store1[size1][0]=i;
                store1[size1][1]=j;
                size1++;

            }
        }
    }
    if(size1==n*m||size0==n*m){
    
        return -1;
    }
    int max=0;
    for(i=0;i<size0;i++){
    
        int x=store0[i][0];
        int y=store0[i][1];
        int min=2000;
        for(j=0;j<size1;j++){
    
            int d=abs(store1[j][0]-x)+abs(store1[j][1]-y);
            if(d<min){
    
                min=d;
            }
        }
        if(min>max){
    
            max=min;
        }
    }
    return max;

}