1 solutions

  • 0
    @ 2024-12-11 0:09:07

    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;
    }
    

    Pascal :

    const dx:array[1..4]of longint=(1,-1,0,0);
          dy:array[1..4]of longint=(0,0,-1,1);
    var
       n,m,i,j,ans:longint;
       c:array[0..100,0..105]of char;
       b:array[0..100,0..105]of boolean;
       s:string;
    procedure dfs(x,y:longint);
    var
       i,h,t,x1,y1,tx,ty:longint;
       q:array[0..10000,1..2]of longint;
    begin
     h:=1;t:=1;
     q[t][1]:=x;q[t][2]:=y;
     b[x,y]:=true;
     while h<=t do
      begin
       x1:=q[h][1];y1:=q[h][2];
       for i:=1 to 4 do
        begin
         tx:=x1+dx[i];ty:=y1+dy[i];
         if (tx>0)and(tx<=n)and(ty>0)and(ty<=m)and(c[tx,ty]>'0')
            and(b[tx,ty]=false)then
             begin
              inc(t);
              q[t][1]:=tx;q[t][2]:=ty;
              b[tx,ty]:=true;
             end;
        end;
       inc(h);
      end;
    end;
    begin
     readln(n,m);
     for i:=1 to n do
      begin
       readln(s);
       for j:=1 to m do c[i,j]:=s[j];
      end;
     fillchar(b,sizeof(b),false);
     for i:=1 to n do
      for j:=1 to m do
       if (c[i,j]>'0')and(b[i,j]=false)then
        begin
         dfs(i,j);
         inc(ans);
        end;
     writeln(ans);
    end.
    

    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

    Information

    ID
    665
    Time
    1000ms
    Memory
    128MiB
    Difficulty
    (None)
    Tags
    # Submissions
    0
    Accepted
    0
    Uploaded By