技术教程 编程教程 八连通（vector动态数组法） 正文

八连通（vector动态数组法）

2023-02-21,,

题目和一般的八连通一样，但行数和列数未定，相乘对于1e6，直接开a[1e6][1e6]的数组肯定会爆内存。用二维的动态vector就能很好的解决这个问题

#include<bits/stdc++.h>

using namespace std;

int dx[]={-,,,-,,-,,};

int dy[]={,,,,,-,-,-};

int n,m;

void dfs(vector< vector < bool > >&a,int x,int y)

{

    a[x][y]=;

    int X,Y;

    for(int i=;i<;i++)

    {

        X=x+dx[i];

        Y=y+dy[i];

        if(X>=&&X<n&&Y>=&&Y<m&&a[X][Y]==)

        {

            dfs(a,X,Y);

        }

    }

    //return ;

}

int main()

{

int x,cnt=;

cin>>n>>m;

//vector<vector<int> > a(n, vector<int>(m,0));

vector< vector<bool> >a(n);

for(int i=;i<n;i++)

{

    a[i].resize(m);

}

for(int i=;i<n;i++)

{

    for(int j=;j<m;j++)

    {

    cin>>x;

    a[i][j]=x;

}

}

for(int i=;i<n;i++)

{

    for(int j=;j<m;j++)

    {

  if(a[i][j]==)

  {

  dfs(a,i,j);

  cnt++;

}

}

}

cout<<cnt<<endl;

}

八连通（vector动态数组法）的相关教程结束。

《八连通（vector动态数组法）.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!