NC185. 岛屿的最大面积
描述
示例1
输入:
[[1,0],[0,1]]
输出:
1
说明:
如题面解释示例2
输入:
[[1,1],[1,0]]
输出:
3
说明:
如题面解释示例3
输入:
[[0]]
输出:
0
C++ 解法, 执行用时: 3ms, 内存消耗: 404KB, 提交时间: 2022-04-18
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param grid int整型vector<vector<>>
* @return int整型
*/
int maxAreaIsland(vector<vector<int> >& grid) {
// write code here
int nr = grid.size();
if(nr == 0) return 0;
int nc = grid[0].size();
int nums_island = 0;
int max_s = 0;
for(int r = 0; r < nr; ++r)
{
for(int c = 0; c < nc; ++c)
{
int mianji = 0;
if(grid[r][c] == 1)
{
++nums_island;
mianji++;
grid[r][c] = 0;
queue<pair<int, int>> qq;
qq.push({r, c});
while(!qq.empty())
{
auto rc = qq.front();
qq.pop();
int row = rc.first, col = rc.second;
if(row - 1 >= 0 && grid[row-1][col] == 1)
{
qq.push({row - 1, col});
grid[row - 1][col] = 0;
mianji++;
}
if(row + 1 < nr && grid[row + 1][col] == 1)
{
qq.push({row + 1, col});
grid[row + 1][col] = 0;
mianji++;
}
if(col - 1 >= 0 && grid[row][col - 1] == 1)
{
qq.push({row, col - 1});
grid[row][col - 1] = 0;
mianji++;
}
if(col + 1 < nc && grid[row][col + 1] == 1)
{
qq.push({row, col + 1});
grid[row][col + 1] = 0;
mianji++;
}
}
max_s = max(max_s, mianji);
}
}
}
return max_s;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 408KB, 提交时间: 2022-05-08
class Solution {
public:
int maxAreaIsland(vector<vector<int> >& grid) {
int nr = grid.size();
if (nr == 0) return 0;
int nc = grid[0].size();
int nums_island = 0;
int max_s = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
int mianji = 0;
if (grid[r][c] == 1) {
++nums_island;
mianji++;
grid[r][c] = 0;
queue<pair<int, int>> qq;
qq.push({r, c});
while (!qq.empty()) {
auto rc = qq.front();
qq.pop();
int row = rc.first, col = rc.second;
if (row - 1 >= 0 && grid[row - 1][col] == 1) {
qq.push({row - 1, col});
grid[row - 1][col] = 0;
mianji++;
}
if (row + 1 < nr && grid[row + 1][col] == 1) {
qq.push({row + 1, col});
grid[row + 1][col] = 0;
mianji++;
}
if (col - 1 >= 0 && grid[row][col - 1] == 1) {
qq.push({row, col - 1});
grid[row][col - 1] = 0;
mianji++;
}
if (col + 1 < nc && grid[row][col + 1] == 1) {
qq.push({row, col + 1});
grid[row][col + 1] = 0;
mianji++;
}
}
max_s = max(max_s, mianji);
}
}
}
return max_s;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 412KB, 提交时间: 2022-02-18
class Solution {
public:
int vis[55][55]={0};//判断是否访问过
int a[4][2]={{-1,0},{0,1},{1,0},{0,-1}};//四个方向
int res=0,n,m;
int cnt;
int maxAreaIsland(vector<vector<int> >& grid) {
n=grid.size();
if(n==0)
return 0;
m=grid[0].size();
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(vis[i][j]==0&&grid[i][j]==1){//如果未访问过，则访问
bfs(i,j,grid);
res=max(cnt,res);//维护最大值
}
}
}
return res;
}
void bfs(int x,int y,vector<vector<int> >& grid){
queue<pair<int,int>> q;//队列
q.push({x,y});//入队
vis[x][y]=1;
cnt=1;//面积初始化为1
while(!q.empty()){
auto t=q.front();
q.pop();//出队
for(int i=0;i<4;i++){//遍历四个方向
int nx=t.first+a[i][0],ny=t.second+a[i][1];
if(nx<0||nx>=n||ny<0||ny>=m){//下标越界判断
continue;
}
if(vis[nx][ny]==0&&grid[nx][ny]==1){//如果未访问过，则访问
q.push({nx,ny});
vis[nx][ny]=1;
cnt++;
}
}
}
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 428KB, 提交时间: 2022-06-10
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param grid int整型vector<vector<>>
* @return int整型
*/
void dfs(vector<vector<int> >& grid, int i, int j, int r, int c)
{
int counter = 0 ;
queue<pair<int,int>> mq;
pair<int,int> p;
mq.push(pair<int,int>(i,j));
counter++;
while(!mq.empty())
{
p = mq.front();
grid[p.first][p.second] = 0;
if(p.first-1>=0)
{
if(grid[p.first-1][p.second]==1)
{
counter++;
grid[p.first-1][p.second] = 0;
mq.push(pair<int,int>(p.first-1, p.second));
}
}
if(p.first+1<r)
{
if(grid[p.first+1][p.second]==1)
{
counter++;
grid[p.first+1][p.second] = 0;
mq.push(pair<int,int>(p.first+1, p.second));
}
}
if(p.second-1>=0)
{
if(grid[p.first][p.second-1]==1)
{
counter++;
grid[p.first][p.second-1] = 0;
mq.push(pair<int,int>(p.first, p.second-1));
}
}
if(p.second+1<c)
{
if(grid[p.first][p.second+1]==1)
{
counter++;
grid[p.first][p.second+1] = 0;
mq.push(pair<int,int>(p.first, p.second+1));
}
}
mq.pop();
}
if(counter>maxi)
maxi = counter;
}
int maxi = 0;
int maxAreaIsland(vector<vector<int> >& grid) {
// write code here
int r = grid.size(), c = grid[0].size();
for(int i=0;i<r;i++)
for(int j=0;j<c;j++)
{
if(grid[i][j]==1)
{
dfs(grid,i,j,r,c);
}
}
return maxi;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 432KB, 提交时间: 2022-02-23
class Solution {
public:
int enc(int i,int j,int sz){
return i*sz+j;
}
// 获取并查集根
int getfa(vector<pair<int,int> > & v2fc, int i){
if(i == v2fc[i].first)return i;
int r = getfa(v2fc, v2fc[i].first);
v2fc[i] = v2fc[r];
return r;
}
// 合并并查集并返回合并后的大小
int merge(vector<pair<int,int> > & v2fc,int i,int j){
auto ri = getfa(v2fc,i);
auto rj = getfa(v2fc,j);
if(ri == rj)return v2fc[ri].second; // 本就是一个
// 合并 rj为新的根
v2fc[rj].second += v2fc[ri].second; // 更新并查集点数
v2fc[ri] = v2fc[rj];
return v2fc[rj].second;
}
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param grid int整型vector<vector<>>
* @return int整型
*/
int maxAreaIsland(vector<vector<int> >& grid) {
// 块 => 并查集父节点(father)，并查集大小(count)
// 只有根是自己的 second才是准确的，根不是自己的节点的second是无效值
vector<pair<int,int> > v2fc(grid.size()*grid[0].size());
for(int i = 0;i<v2fc.size();i++){
v2fc[i] = {i,1};
}
int area = 0;
int di[] = {1,0};
int dj[] = {0,1};
for(int i = 0;i<grid.size();i++){
for(int j = 0;j<grid[0].size();j++){
if(grid[i][j] == 0)continue;
area = max(area,1); // 没有两两相连的情况
for(int k = 0;k < 2;k++){ // 两个方向
auto ni = i + di[k]; // 相邻坐标的i
auto nj = j + dj[k]; // 相邻坐标的j
// 坐标不合法
if(ni >= grid.size() || nj >= grid[0].size() )continue;
// 非1
if(grid[ni][nj] == 0)continue;
area = max(
area,
merge(
v2fc,
enc(i,j,grid[0].size()),
enc(ni,nj,grid[0].size())
)
);
}
}
}
return area;
}
};