【每日刷题】Day156
🥕个人主页：开敲🍉
🔥所属专栏：每日刷题🍍
🌼文章目录🌼
1. 1020. 飞地的数量 - 力扣(LeetCode)
2. 1765. 地图中的最高点 - 力扣(LeetCode)
3. 1162. 地图分析 - 力扣(LeetCode)
1. 1020. 飞地的数量 - 力扣(LeetCode)
//思路：多源BFS
//题目问有多少陆地没法跨越边界，我们逆向思考：从边界上的陆地出发，能够到达哪些陆地。将能够到达的陆地标记为已访问。
//最后遍历原数组，遇到陆地并且没有被标记过，说明从边界的陆地没法到达这，结果+1。
class Solution {
public:
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int numEnclaves(vector<vector<int>>& grid)
{
int n = grid.size(),m = grid[0].size();
vector<vector<bool>> hash(n,vector<bool>(m));
queue<pair<int,int>> qu;
//遍历边界的陆地
for(int i = 0;i<n;i++)
{
if(grid[i][0])
{
qu.push({i,0});
hash[i][0] = true;
}
if(grid[i][m-1])
{
qu.push({i,m-1});
hash[i][m-1] = true;
}
}
for(int j = 0;j<m;j++)
{
if(grid[0][j])
{
qu.push({0,j});
hash[0][j] = true;
}
if(grid[n-1][j])
{
qu.push({n-1,j});
hash[n-1][j] = true;
}
}
while(!qu.empty())
{
int size = qu.size();
for(int i = 0;i<size;i++)
{
auto tmp = qu.front();
qu.pop();
for(int j = 0;j<4;j++)
{
int x = tmp.first+dx[j],y = tmp.second+dy[j];
if(x>=0&&x<n&&y>=0&&y<m&&!hash[x][y]&&grid[x][y])
{
qu.push({x,y});
hash[x][y] = true;//标记从边界陆地能够到达的陆地
}
}
}
}
int ans = 0;
for(int i = 0;i<n;i++)
for(int j = 0;j<m;j++)
if(grid[i][j]&&!hash[i][j]) ans++;//没有标记的陆地说明没法到达边界
return ans;
}
};
2. 1765. 地图中的最高点 - 力扣(LeetCode)
//思路：多源BFS
//将所有水域视为一个起点，同时向外扩展，每次上、下、左、右 扩展到陆地时，陆地的高度都 ＝ 前一个位置的高度 + 1
class Solution {
public:
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
vector<vector<int>> highestPeak(vector<vector<int>>& iw)
{
int n = iw.size(),m = iw[0].size();
vector<vector<bool>> hash(n,vector<bool>(m));
queue<pair<int,int>> qu;
for(int i = 0;i<n;i++)//将所有水域入队列，并将水域的高度设为0
for(int j = 0;j<m;j++)
if(iw[i][j])
{
iw[i][j] = 0;
qu.push({i,j});
hash[i][j] = true;
}
while(!qu.empty())
{
int size = qu.size();
for(int i = 0;i<size;i++)
{
auto tmp = qu.front();
int bx = tmp.first,by = tmp.second;//前一个位置
qu.pop();
for(int j = 0;j<4;j++)
{
int x = bx+dx[j],y = by+dy[j];
if(x>=0&&x<n&&y>=0&&y<m&&!hash[x][y])
{
iw[x][y] = iw[bx][by]+1;//扩展到陆地时，当前位置高度 = 前一个位置高度 + 1
qu.push({x,y});
hash[x][y] = true;
}
}
}
}
return iw;
}
};
3. 1162. 地图分析 - 力扣(LeetCode)
//思路：多源BFS
//本题直接做法是将所有 0（海洋）看作一个起点向外扩展，每次向外扩展一层计数器 sum++，当扩展到陆地时，前一个位置的距离 = sum。但是这个做法不太好，因为我们判断是否为陆地就是判断 值 == 1 || 值 > 0，但是如果我们将海洋的值修改为了距离 sum，sum一定 ＞ 0 && sum == 1存在，这就会和陆地混淆。
//将所有的陆地看作一个起点向外扩展，同样的每扩展一层计数器 sum++。当扩展到海洋时，前一个位置的距离 = sum，这种做法比较好，我们判断是否扩展到海洋就是判断 值 == 0，陆地 = 1，sum的值也一定 > 0，因此不会混淆。
class Solution {
public:
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int maxDistance(vector<vector<int>>& grid)
{
int n = grid.size(),m = grid[0].size();
vector<vector<bool>> hash(n,vector<bool>(m));
queue<pair<int,int>> qu;
int flag1 = 0,flag2 = 0;//flag1和flag2用于判断地图中是否只存在陆地 或者 海洋
for(int i = 0;i<n;i++)
for(int j = 0;j<m;j++)
{
if(grid[i][j])//将所有陆地视为一个起点
{
qu.push({i,j});
hash[i][j] = true;
flag1 = 1;
}
else flag2 = -1;
}
if(flag1*flag2!=-1) return -1;//如果存在陆地和海洋，flag1*flag2就是 -1，否则只存在陆地 或者 海洋。
int sum = 0;
while(!qu.empty())
{
sum++;
int size = qu.size();
for(int i = 0;i<size;i++)
{
auto tmp = qu.front();
int bx = tmp.first,by = tmp.second;
qu.pop();
for(int j = 0;j<4;j++)
{
int x = bx+dx[j],y = by+dy[j];
if(x>=0&&x<n&&y>=0&&y<m&&!hash[x][y])
{
if(!grid[x][y]) grid[bx][by] = sum;//当扩展到海洋时，当前位置距离海洋的距离 = sum
qu.push({x,y});
hash[x][y] = true;
}
}
}
}
int ans = 0;
for(int i = 0;i<n;i++)
for(int j = 0;j<m;j++)
ans = ans>grid[i][j]?ans:grid[i][j];//返回距离陆地最远的海洋的距离
return ans;
}
};
