1162. 地图分析-非递归法

1162. 地图分析

你现在手里有一份大小为 n x n 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地。

请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。

我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。

示例 1：

输入：grid = [[1,0,1],[0,0,0],[1,0,1]]
输出：2
解释：
海洋单元格 (1, 1) 和所有陆地单元格之间的距离都达到最大，最大距离为 2。

示例 2：

输入：grid = [[1,0,0],[0,0,0],[0,0,0]]
输出：4
解释：
海洋单元格 (2, 2) 和所有陆地单元格之间的距离都达到最大，最大距离为 4。

对于这一题，我们如果不使用递归方法，那么就使用两个数组存储0和1的坐标，然后进行计算，可以减少计算开销，但是这样的方法，仍未达到最优，可以进一步的判断计算停止，解题代码如下：

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;

}