我自闭了...

常规
1

2. 我自闭了

XJOI - 题目ID：8010选做题100分

最新提交：0 分

历史最高：0 分

时间限制: 200ms

空间限制: 32000kB

题目描述

时间限制：0.2s 空间：32M

题目描述：

坠落在茫茫的毒瘤之海中，你自闭了。

但是小马哥不会自闭。

小马哥给了你一份毒瘤之海的地图，有 n 行 m 列，行号从 1 到 n，列号从 1 到 m。如果两个格子上下左右相邻，称为连通。例如 (x, y) 和 (x-1, y) (x+1, y) (x, y-1) (x, y+1) 都相邻。

每一个格子里面可能有毒瘤，也可能没有。毒瘤用 1 表示，否则用 0 表示。定义一个毒瘤连通块：任意两个毒瘤点都可以通过相邻连通关系互相到达的一个区块。那么请问最大的毒瘤连通块包含多少个毒瘤点。

可以参见样例详细理解题意。

输入格式：

第一行 n, m。(1≤n,m≤50)

接下来 n 行，每行 m 个 0 或 1。

输出格式：

一个数表示答案。

样例输入1：

5 4 
0101 
0111 
1000 
1100 
0101

样例输出1：

5
2 
#include <bits/stdc++.h>
using namespace std;
int n,m;
char a[105][105];
int vis[105][105],cnt;
int dx[8]={0,-1,0,1};
int dy[8]={-1,0,1,0};
int x;
void dfs(int x,int y){
    cnt++;
    for(int i=0;i<4;i++){
        int xx=x+dx[i],yy=y+dy[i];
        if(xx<1||xx>n||yy<1||yy>m||a[xx][yy]=='0') continue;
        a[xx][yy]='0';
        dfs(xx,yy);
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]=='1'){
            	cnt=0;
                a[i][j]='0';
                dfs(i,j);
                x=max(x,cnt);
            }
        }
    }
    cout<<x;
}
2 个赞
4 
#include<bits/stdc++.h>
using namespace std;
int n,m,sum,ans=0;
int nxt[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
char a[101][101];
void dfs(int x,int y){
	a[x][y]='0';
	sum++;
	for(int i=0;i<4;i++){
		int tx=x+nxt[i][0];
		int ty=y+nxt[i][1];
		if(tx<1||tx>n|ty<1||ty>m) continue;
		if(a[tx][ty]=='1')
		{
			dfs(tx,ty);
			
		}
	}
} 

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]=='1'){
				sum=0;
				dfs(i,j);
				ans=max(ans,sum);
			}
		}
	}
	cout<<ans;
    return 0; 
}
1 个赞