LeetCode 1162. 地图分析

思路：从所有陆地同时开始bfs，维护距离矩阵d，最后从d中找出最大值即为所求

class Solution {
private:
	const int inf=1e8;
	typedef pair<int,int> P;
	int d[100][100],dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
public:
    int maxDistance(vector<vector<int>>& grid) {
    	int n=grid.size();
    	queue<P>q; 
    	for(int i=0;i<n;i++)
        	for(int j=0;j<n;j++){
            	if(!grid[i][j]) d[i][j]=inf;//海洋距离初始化为inf，陆地为0
            	else q.push(P(i,j));//所有陆地入队
        	}
    	if(q.size()==0||q.size()==n*n) return -1;//全是海洋或陆地
    	while(!q.empty()){
        	P p=q.front(); q.pop();        
        	for(int i=0;i<4;i++){
            	int nx=p.first+dx[i],ny=p.second+dy[i];
            	if(0<=nx&&nx<n&&0<=ny&&ny<n&&d[nx][ny]==inf){
                	q.push(P(nx,ny)); d[nx][ny]=d[p.first][p.second]+1;
            	}
        	}  
    	}
    	//找出距离矩阵d中的最大值
    	int max=0;
    	for(int i=0;i<n;i++)
        	for(int j=0;j<n;j++)
            	if(max<d[i][j]) max=d[i][j];
    	return max;
	}
};