DD12. 几个岛
描述
输入描述
多组测试数据，请参考例题处理 每组数据k+3行, k表示addLand操作次数 第一行:表示行数m 第二行:表示列数n 第三行:表示addLand操作次数k 第4~k+3行:row col 表示addLand的坐标。注意超过边界的坐标是无效的。输出描述
一行,k个整数, 表示每次addLand操作后岛屿的个数, 用空格隔开，结尾无空格示例1
输入:
3 3 4 0 0 0 1 1 2 2 1
输出:
1 1 2 3
C 解法, 执行用时: 1ms, 内存消耗: 376KB, 提交时间: 2020-07-31
#include<stdio.h>
int main()
{
int i,j,m,n,k,x,y,a[500][500],row[500],col[500],count=0,flag=1;
int c_point=0; //储存陆地单元格的相邻陆地个数；
scanf("%d %d %d",&m,&n,&k);
for(i=0;i<=m+1;i++) //初始化海水单元格为0；
{
for(j=0;j<=n+1;j++)
{
a[i][j]=0;
}
}
for(i=1;i<=k;i++) //储存输入的陆地单元格x,y坐标
{
scanf("%d %d",&x,&y);
row[i]=x+1;
col[i]=y+1;
}
for(i=1;i<=k;i++) //依次求出岛屿的个数
{
x=row[i];
y=col[i];
if(x>m||y>n)
{
printf("%d ",count);
}
else{
if(a[x][y]==1)
{
printf("%d ",count);
}
if(a[x][y]!=1)
{
a[x][y]=1;
c_point=0;
c_point=a[x-1][y]+a[x][y-1]+a[x][y+1]+a[x+1][y];
if(c_point==0)
{
count++;
}
if(c_point==2&&count!=1)
{
count--;
}
if(c_point==3)
{
count=count-2;
}
if(c_point==4)
{
count=count-3;
}
if(count!=0)
{
printf("%d ",count);
}
if(count==0)
{
count++;
printf("%d ",count);
}
}
}
}
return 0;
}
C++ 解法, 执行用时: 2ms, 内存消耗: 352KB, 提交时间: 2018-08-24
#include <iostream>
#include <string>
#include <math.h>
#include <vector>
using namespace std;
struct Point
{
int x, y;
Point(int _x, int _y) :x(_x), y(_y){}
};
int main()
{
int r, c, n;
cin >> r >> c >> n;
string res;
vector<vector<Point>> points;
int land_number = 0;
while (n--)
{
int x, y;
cin >> x >> y;
if (x >= 0 && x < r && y >= 0 && y < c)
{
bool flag = true;
int i,index = -1;
Point tmp(x, y);
for (i = 0; i < points.size(); i++)
{
for (int j = 0; j < points[i].size(); j++)
{
Point& cur = points[i][j];
if (flag)
{
if (cur.x == x && abs(cur.y - y) <= 1 || cur.y == y && abs(cur.x - x) <= 1)
{
flag = false;
points[i].push_back(tmp);
index = i;
break;
}
}
else
{
if (cur.x == x && abs(cur.y - y) <= 1 || cur.y == y && abs(cur.x - x) <= 1)
{
points[index].insert(points[index].end(), points[i].begin(), points[i].end());
points.erase(points.begin() + i);
land_number--;
i--;
break;
}
}
}
}
if (flag)
{
vector<Point> tmpV;
tmpV.push_back(tmp);
land_number++;
points.push_back(tmpV);
}
}
res += (land_number + '0');
if (n == 0)
break;
res += " ";
}
cout << res << endl;
return 0;
}
C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2021-03-03
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <vector>
using namespace std;
int main()
{
int m,n,k;
cin >> m >> n >> k;
vector<vector<int>> nums(m,vector<int>(n,0));
vector<int> res;
int count = 0;
for(int i = 0; i < k; i++)
{
int zeros = 0;
int a,b;
cin >> a >> b;
if(a < 0 || b < 0 || a >=m || b >=n || nums[a][b] ==1)
{
res.push_back(count);
}else{
nums[a][b] = 1;
for(int j = b-1; j < n && j <= b+1; j+=2)
{
if(j >= 0 && nums[a][j] == 1){
zeros++;
}
}
for(int j = a-1; j < m && j <= a+1; j+=2)
{
if(j >= 0 && nums[j][b] == 1)
{
zeros ++;
}
}
count = max(count-zeros+1,1);
res.push_back(count);
}
}
for(int i = 0; i < k; i++)
{
cout << res[i] << " ";
}
}
C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2020-10-31
#include <iostream>
#include <string>
#include <math.h>
#include <vector>
using namespace std;
struct Point
{
int x, y;
Point(int _x, int _y) :x(_x), y(_y){}
};
int main()
{
int r, c, n;
cin >> r >> c >> n;
string res;
vector<vector<Point>> points;
int land_number = 0;
while (n--)
{
int x, y;
cin >> x >> y;
if (x >= 0 && x < r && y >= 0 && y < c)
{
bool flag = true;
int i,index = -1;
Point tmp(x, y);
for (i = 0; i < points.size(); i++)
{
for (int j = 0; j < points[i].size(); j++)
{
Point& cur = points[i][j];
if (flag)
{
if (cur.x == x && abs(cur.y - y) <= 1 || cur.y == y && abs(cur.x - x) <= 1)
{
flag = false;
points[i].push_back(tmp);
index = i;
break;
}
}
else
{
if (cur.x == x && abs(cur.y - y) <= 1 || cur.y == y && abs(cur.x - x) <= 1)
{
points[index].insert(points[index].end(), points[i].begin(), points[i].end());
points.erase(points.begin() + i);
land_number--;
i--;
break;
}
}
}
}
if (flag)
{
vector<Point> tmpV;
tmpV.push_back(tmp);
land_number++;
points.push_back(tmpV);
}
}
res += (land_number + '0');
if (n == 0)
break;
res += " ";
}
cout << res << endl;
return 0;
}
C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2020-08-20
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
int m,n,k;
int r,c;
while(cin>>m>>n>>k){
vector<vector<int>> matrixs(m,vector<int>(n,0));
vector<vector<int>> nums(k,vector<int>(2));//每次改变的地方
vector<int> res;//每次addland操作后的岛屿个数
for(int i=0;i<k;i++){
cin>>r;
cin>>c;
nums[i][0]=r;
nums[i][1]=c;//存储可能出现岛屿的地方
}
//单个进行处理
//看是否和之前的岛屿相连（上下左右），相连岛屿数不变，不相连，岛屿数+1
int cnt=0;
for(int i=0;i<k;i++){
int a=nums[i][0];
int b=nums[i][1];
if(a<0||b<0||a>=m||b>=n){
//判断是否越界，如果越界，岛屿数不变
res.push_back(cnt);//岛屿数不变
continue;//跳出此次for循环，到下一次循环
}
//判断当前的点是否之前已经是岛屿了
if(matrixs[a][b]==1){
res.push_back(cnt);//岛屿数不变
continue;//跳出此次for循环，到下一次循环
}
//其他正常情况，设置成一个新的岛屿，上下左右遍历看是否和之前的岛屿相连，相连则岛屿数-1，最后+1表示连在一起
matrixs[a][b]=1;//没有越界，且是一个新的点，则将其置1
if(a-1>=0&&matrixs[a-1][b]==1){
if(cnt!=0)
cnt--;//若该新点为桥，将岛屿数减1
}
if(a+1<m&&matrixs[a+1][b]==1){
if(cnt!=0)
cnt--;//注意都是并列的
}
if(b-1>=0&&matrixs[a][b-1]==1){
if(cnt!=0)
cnt--;
}
if(b+1<n&&matrixs[a][b+1]==1){
if(cnt!=0)
cnt--;
}
cnt++;//最后综合加上1
res.push_back(cnt);
}
for(int i=0;i<res.size()-1;i++)
cout<<res[i]<<" ";
cout<<res[k-1]<<endl;
}
return 0;
}