题目描述

include[HTML_REMOVED]

using namespace std;

typedef pair[HTML_REMOVED] pii;
const int N = 100;

int m[N][N]; //存地图
int n,m_; //地图的长与宽
int ans = 0;
//判重数组，即是否走过的路
bool st_road[N][N]; //判断陆地走过了没
bool st_sea[N][N]; //判断海洋走过了没

//方向变量
//查找海洋的
int dx[8] = {-1,-1,-1,0,1,1,1,0};
int dy[8] = {-1,0,1,1,1,0,-1,-1};

//查找陆地的
int ddx[4] = {-1,0,1,0};
int ddy[4] = {0,1,0,-1};

//判断是否越界
bool check(int x,int y){
return (x>=0 && x < n &&y >=0 &&y < m_);
}

//找到X，y所在的岛屿，并将它们标记为true
void bfs_road(int x,int y){
queue[HTML_REMOVED]q;
st_road[x][y] = true;
q.push({x,y});
while(q.size()){
auto t = q.front();
q.pop();
for(int i = 0;i<4;i++){
int nx = t.first + ddx[i];
int ny = t.second + ddy[i];
//第二个条件的作用是确定该点是海洋还是陆地
if(check(nx,ny) && m[nx][ny] && !st_road[nx][ny]){
st_road[nx][ny] = true;
q.push({nx,ny});
}
}

}

}

void bfs_sea(int x,int y){
queue[HTML_REMOVED]q;
st_sea[x][y] = true;
q.push({x,y});
while(q.size()){
auto t = q.front();
q.pop();
for(int i = 0;i < 8;i++){
int nx = t.first + dx[i];
int ny = t.second +dy[i];

        if(check(nx,ny) && !m[nx][ny] && !st_sea[nx][ny] ){
            st_sea[nx][ny] = true;
            q.push({nx,ny});
        }

        if(check(nx,ny) && m[nx][ny] && !st_road[nx][ny]){
            ans++;
            bfs_road(nx,ny);

        }
    }
}

}

void solve(){
cin>>n>>m_;

ans = 0;
for(int i = 0;i<=n;i++){
    for(int j = 0; j <= m_;j++)
        st_sea[i][j] = st_road[i][j] = false;
}

for(int i = 0;i<n;i++){
    string s;cin>>s;
    for(int j = 0;j < m_;j++)
        m[i][j] = s[j] - '0';       
}

bool flag = false;

for(int i =0;i<n;i++){
    for(int j = 0;j<m_;j++){
        if(!i || i== n-1 || !j || j==m_-1){
            if(!m[i][j] && !st_sea[i][j]){
                flag =true;
                bfs_sea(i,j);
            }
        }
    }
}

if(!flag) ans = 1;

cout<<ans<<endl;

}

int main(){
int t = 1;
cin>>t;
while(t–)
solve();
}

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla