地图分析

地图分析
将所有陆地作为源点，进行dijsktra，最后dist[i][j]表示grid[i][j]距离源点最短路径

class Solution {
    int[] dx={0,1,0,-1};
    int[] dy={1,0,-1,0};
    public int maxDistance(int[][] grid) {
        //多源最短路
        int n=grid.length;int m=grid[0].length;
        int[][] dist=new int[n][m];
        for(int i=0;i<n;i++){
            Arrays.fill(dist[i],Integer.MAX_VALUE);
        }
        boolean[][] vis=new boolean[n][m];
        Queue<int[]> queue=new LinkedList<int[]>();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(grid[i][j]==1){
                    queue.offer(new int[]{0,i,j});
                    vis[i][j]=true;
                }
            }
        }
        while(!queue.isEmpty()){
            int[] node=queue.poll();
            int d=node[0];int x=node[1];int y=node[2];
            for(int k=0;k<4;k++){
                int a=x+dx[k];
                int b=y+dy[k];
                if(a<0||a>=n||b<0||b>=m||vis[a][b]){
                    continue;
                }
                if(dist[a][b]>dist[x][y]+1){
                    dist[a][b]=dist[x][y]+1;
                    vis[a][b]=true;
                    queue.offer(new int[]{dist[a][b],a,b});
                }
            }
        }
        int res=Integer.MIN_VALUE;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                res=Math.max(res,dist[i][j]);
            }
        }
        return res==Integer.MIN_VALUE? -1:res;
    }
}

方式二：dp

dp[i][j]:分别从左上、右下进行dp

class Solution {
    public int maxDistance(int[][] grid) {
        int n=grid.length;int m=grid[0].length;
        int[][] dp=new int[n][m];
        int INF=0x3f3f3f;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                dp[i][j]=grid[i][j]==1? 0:INF;
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(grid[i][j]==1){
                    continue;
                }
                if(i>=1){
                    dp[i][j]=Math.min(dp[i][j],dp[i-1][j]+1);
                }
                if(j>=1){
                    dp[i][j]=Math.min(dp[i][j],dp[i][j-1]+1);
                }
            }
        }
        for(int i=n-1;i>=0;i--){
            for(int j=n-1;j>=0;j--){
                if(grid[i][j]==1){
                    continue;
                }
                if(i+1<n){
                    dp[i][j]=Math.min(dp[i][j],dp[i+1][j]+1);
                }
                if(j+1<n){
                    dp[i][j]=Math.min(dp[i][j],dp[i][j+1]+1);
                }
            }
        }
        int ans=-1;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(grid[i][j]==0){
                    ans=Math.max(ans,dp[i][j]);
                }
            }
        }
        if(ans==INF){
            return -1;
        }else{
            return ans;
        }
    }
}