1 条题解

  • 0
    @ 2024-12-24 9:48:48

    C++ :

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    
    using namespace std;
    int a[100][100],ans,m,n;
    const int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
    struct queh
    {
    	int x,y;
    }que[100*100];
    void init()
    {
    	cin>>m>>n;
    	
    	for(int i=1;i<=m;i++)
    	{
    		for(int j=1;j<=n;j++)
    			scanf("%1d",&a[i][j]);
    	}
    }
    void bfs(int x,int y)
    {
    	int head=0,tail=1;
    	que[head].x=x,que[head].y=y;
    	a[x][y]=0;
    	while(head!=tail)
    	{
    		for(int i=0;i<4;i++)
    		{
    			int nx=que[head].x+dx[i],ny=que[head].y+dy[i];
    			if(a[nx][ny]&&nx>0&&ny>0&&nx<=m&&ny<=n)
    			{
    				//add(nx,ny);
    				queh t;
    				t.x=nx,t.y=ny;
    				que[tail++]=t;
    				a[nx][ny]=0;
    			}
    		}
    		head++;
    	}
    }
    void print()
    {
    	printf("%d",ans);
    }
    int main()
    {
    	init();
    	for(int i=1;i<=m;i++)
    	for(int j=1;j<=n;j++)
    	 if(a[i][j]!=0){
    	 	bfs(i,j);
    		 ans++;	
    	 }
    	print();
    	return 0;
    }
    

    Java :

    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Scanner;
    
    
    public class Main {
    	static char[][] map;
    	static int[][] d;
    	static int m,n;
    	public static void main(String[] args) {
    		Scanner in = new Scanner(System.in);
    		while (in.hasNextInt()) {
    			m = in.nextInt();
    			n = in.nextInt();
    			map = new char[m][n];
    			d = new int[m][n];
    			for (int i = 0; i < m; i++) {
    				String s = in.next();
    				for (int j = 0; j < n; j++) {
    					map[i][j] = s.charAt(j);
    				}
    			}
    			int cnt = 0;
    			for(int i=0;i<m;i++){
    				for(int j=0;j<n;j++){
    					if(map[i][j]!='0'&&d[i][j]==0)	
    						dfs(i,j,++cnt);
    				}
    			}
    			System.out.println(cnt);
    		}
    	}
    	public static void dfs(int r,int c,int id){
    		if(r<0||r>=m||c<0||c>=n)
    			return;
    		if(d[r][c]>0 || map[r][c]=='0')
    			return;
    		d[r][c] = id;
    		dfs(r+1,c,id);
    		dfs(r-1,c,id);
    		dfs(r,c+1,id);
    		dfs(r,c-1,id);
    	}
    }
    
    
    • 1

    信息

    ID
    719
    时间
    1000ms
    内存
    128MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者