BFS

连通块的最好的解决方法就是BFS，对于每一个1我们都进行一次BFS，把连通的1变成0，答案就是BFS后的1的个数

• 问题①：坐标如何存储？我们可以用pair或者结构体
• 问题②：BFS如何实现？我们把每个为1的点放到队列中，尝试前后左右走，假如走到1就将其放到队列中。注意vis的标记

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
typedef pair<int,int> PII;

int g[N][N];
bool vis[N][N];
int n,m,cnt;
//方向数组
int tx[] = {0,0,1,-1},ty[] = {1,-1,0,0};

//BFS过程
void bfs(int a,int b)
{
	queue<PII> q;
	q.push({a,b});
	while(!q.empty())
	{
		auto t = q.front();
		q.pop();
		int x = t.first,y = t.second;
		//尝试扩展
		for(int i=0;i<4;i++)
		{
			int rx = x+tx[i],ry = y+ty[i];
			vis[x][y] = false;
			//判断是否越界以及是否为1
			if(g[rx][ry] == 1 && vis[rx][ry] && rx>=1 && rx<=n && ry>=1 && ry<=m)
			{
				g[rx][ry] = 0;
				q.push({rx,ry});
			}
		}
	}
}

int main()
{
	memset(vis,true,sizeof(vis));
	cin >> n >> m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin >> g[i][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			//对于每一个1都进行一次BFS
			if(g[i][j] == 1)
			{
				bfs(i,j);
				cnt++;
			}
	cout << cnt;
	return 0;
}

DFS

对于选考班我觉得还是DFS最能想出来，我们还是对于每个1进行扩展，但是我们不用队列，而是直接递归到下一个点，同时打上标记

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
typedef pair<int,int> PII;

int g[N][N];
bool vis[N][N];
int n,m,cnt;
//方向数组
int tx[] = {0,0,1,-1},ty[] = {1,-1,0,0};

//DFS
void dfs(int a,int b)
{
	//打标记
	vis[a][b] = false;
	for(int i=0;i<4;i++)
	{
		int rx = a+tx[i],ry = b+ty[i];
		//扩展并且判断
		if(rx>=1 && rx<=n && ry>=1 && ry<=m && g[rx][ry] == 1 && vis[rx][ry])
		{
			g[rx][ry] = 0;
			//递归
			dfs(rx,ry);
		}
	}
}

int main()
{
	memset(vis,true,sizeof(vis));
	cin >> n >> m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin >> g[i][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(g[i][j] == 1)
			{
				//对于每一个1都进行一次DFS
				dfs(i,j);
				cnt++;
			}
	cout << cnt;
	return 0;
}

这么多大佬发了题解，本蒟蒻也来发一下

• 核心思想是采用递归的方式进行DFS
• 标记已访问节点的方式是将g数组中对应位置的值改为0
• 时间复杂度为O(nm)
• • 和上面qianmo大佬比起来虽然时间复杂度都是O(nm)，但不必要调用vis

C++

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int g[N][N];
int n, m, cnt;
void dfs(int x, int y){
	if (g[x][y] == 0) return;// 已经访问过的点直接返回
	g[x][y] = 0; // 标记为已访问
	if (x > 1) dfs(x-1, y);
	if (x < n) dfs(x+1, y);
	if (y > 1) dfs(x, y-1);
	if (y < m) dfs(x, y+1);
}


int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> g[i][j];
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (g[i][j] == 1){
				dfs(i, j); cnt++;
			}
	cout << cnt << endl;
	return 0;
}

Python

①

n, m = map(int, input().split())
g = [[0]*(m+1) for i in range(n+1)]
cnt = 0

def dfs(x, y):
    if g[x][y] == 0: return
    g[x][y] = 0
    if x > 1: dfs(x-1, y)
    if x < n: dfs(x+1, y)
    if y > 1: dfs(x, y-1)
    if y < m: dfs(x, y+1)

for i in range(1, n+1):
    line = input().split()
    for j in range(1, m+1):
        g[i][j] = int(line[j-1])
for i in range(1, n+1):
    for j in range(1, m+1):
        if g[i][j] == 1:
            dfs(i, j)
            cnt += 1
print(cnt)

②

Pycharm逼的码风，同样的代码，只是想告诉你我恨Pycharm

n, m = map(int, input().split())
g = [[0]*(m+1) for i in range(n+1)]
cnt = 0


def dfs(x, y):
    if g[x][y] == 0:
        return
    g[x][y] = 0
    if x > 1:
        dfs(x-1, y)
    if x < n:
        dfs(x+1, y)
    if y > 1:
        dfs(x, y-1)
    if y < m:
        dfs(x, y+1)


for i in range(1, n+1):
    line = input().split()
    for j in range(1, m+1):
        g[i][j] = int(line[j-1])
for i in range(1, n+1):
    for j in range(1, m+1):
        if g[i][j] == 1:
            dfs(i, j)
            cnt += 1
print(cnt)

都看到这了还不点个赞🙃

C++

不要脸地发个蓝翔优化题解

#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> PII;
const int N = 105;
int g[N][N];
int n ,m, cnt = 0;

int tx[4] = {1, -1, 0, 0};
int ty[4] = {0, 0, 1, -1}

void BFS(int x, int y){
    queue <PII> q;
    q.push({x, y});
    while(!q.empty()) {
        PII t = q.front();
        q.pop();
        int a = t.first;
        int b = t.second;
        for(int i = 0; i < 4; i++) {
            int rx = a + tx[i];
            int ry = b + ty[i];
            if(rx >= 1 && ry >= 1 && g[rx][ry] == 1) {
                g[rx][ry] = 0;
                q.push({rx, ry});
            }
        }
    }
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> g[i][j];
        }
    }
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= m; j++) {
            if(g[i][j] == 1) {
                BFS(i ,j);
                cnt += 1;
            }
        }
    }
    cout << cnt;
    return 0;
}

《关于题目数据太水以至于递归能过这件事》

#include <bits/stdc++.h>

using namespace std;



int sq[1000][1000];

int dir[5][2] = {{}, {1, 0}, {-1, 0}, {0, 1}, {0, -1}};

int cnt = 2;

int l, w;



void b(int x, int y)

{

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

    {

        int x1 = x + dir[i][1];

        int y1 = y + dir[i][0];

        if (1 <= x1 <= l and 1 <= y1 <= w and sq[x1][y1] == 1)

        {

            sq[x1][y1] = cnt;

            b(x1, y1);

        }

    }

}



signed main()

{

    ios::sync\_with\_stdio(0);

    cin.tie(0);

    cin >> l >> w;

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

    {

        for (int j = 1; j <= w; j++)

        {

            cin >> sq[i][j];

        }

    }

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

    {

        for (int j = 1; j <= w; j++)

        {

            if (sq[i][j] == 1)

            {

                b(i, j);

                cnt++;

            }

        }

    }

    cout<<cnt-2;

}