牛客网 滴滴出行 2018年笔试题

题目描述

给定一个m行n列的二维地图, 初始化每个单元都是水.操作addLand 把单元格(row,col)变成陆地.岛屿定义为一系列相连的被水单元包围的陆地单元, 横向或纵向相邻的陆地称为相连(斜对角不算).在一系列addLand的操作过程中, 给出每次addLand操作后岛屿的个数.二维地图的每条边界外侧假定都是水.

输入描述:

多组测试数据，请参考例题处理 每组数据k+3行, k表示addLand操作次数 第一行:表示行数m 第二行:表示列数n 第三行:表示addLand操作次数k 第4~k+3行:row col 表示addLand的坐标。注意超过边界的坐标是无效的。

输出描述:

一行,k个整数, 表示每次addLand操作后岛屿的个数, 用空格隔开，结尾无空格

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int  countIsland(vector<vector<int> >map,int row,int col);  

int main(){
int m,n,k;
cin >> m >> n >> k;
int island = 0;
vector<vector<int> > a(m);
vector<int> re;
for(int i = 0;i < m;i++){
    a[i].resize(n);
}
for(int i = 0 ; i < m;i++){
    for(int j = 0; j < n;j++){
        a[i][j] = 0;
    } 
} 
for(int i = 0;i < k;i++){
    int row,col;
    cin >> row >> col;
    a[row][col] = 1;
    re.push_back(countIsland(a,m,n));
}
for(vector<int>::iterator it = re.begin();it!= re.end();it++){
    cout << *it << " ";
}
}

int countIsland(vector<vector<int> > a,int row,int col){    
int count = 0;
for(int i = 0 ; i < row; i++){
    for(int j = 0; j < col; j++){
        if( a[i][j] == 1){
            count++;
            queue<pair<int,int> > Queue;
            Queue.push(make_pair(i,j));
            while(Queue.size()!=0){
                pair<int,int> node = Queue.front();
                Queue.pop();
                if(node.first + 1 < row && a[node.first + 1 ][node.second] == 1 ){
                    Queue.push(make_pair(node.first+1,node.second));
                    a[node.first+1][node.second] = 0;   
                }
                if(node.second + 1 < col && a[node.first][node.second+1] == 1){
                    Queue.push(make_pair(node.first,node.second+1));
                    a[node.first][node.second+1] = 0;
                }
                if(node.second - 1 >= 0 && a[node.first][node.second - 1] == 1){
                    Queue.push(make_pair(node.first,node.second-1));
                    a[node.first][node.second - 1] = 0;
                }
                if(node.first - 1 >= 0 && a[node.first - 1][node.second] == 1){
                    Queue.push(make_pair(node.first - 1,node.second));
                    a[node.first - 1][node.second] = 0;
                }
            }
        }   
    }
}
return count;
}

BFS求岛屿的数目。