1 solutions

  • 0
    @ 2024-12-10 22:27:29

    C :

    #include <stdio.h>
    int dir[4][2]={0,1,0,-1,1,0,-1,0};
    int n,m;
    int mat[1005][1005];
    void dfs(int x,int y)
    { 
    mat[x][y]=0; 
    int i,tx,ty; 
    for(i=0;i<4;++i)
     {  
     tx=x+dir[i][0];  
     ty=y+dir[i][1];  
     if(tx<0||tx>=n||ty<0||ty>=m)
     continue;  
     if(mat[tx][ty])   
     dfs(tx,ty); 
     }
     }
     void main()
     {
      while(scanf("%d%d",&n,&m)!=EOF) 
      {  
      int ans  = 0; 
       int i,j; 
        for(i=0;i<n;++i)  
    	 for(j=0;j<m;++j)    
    	 scanf("%1d",&mat[i][j]);  
    	 for(i=0;i<n;++i)  
    	  for(j=0;j<m;++j)    
    	  if(mat[i][j])    
    	  {     
    	  ++ans;     
    	  dfs(i,j);    
    	  }
    	    printf("%d\n",ans); 
    		}
    		}
    

    C++ :

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    struct rec
    {
    	int x,y;
    }f[10001];
    int a[101][101];
    int h,t,n,m,l;
    string s;
    int bfs(int l)
    {
    	int x=f[l].x,y=f[l].y;
    	if(a[x][y]==0) return 0;
    	a[x][y]=0;
    	if(a[x][y+1]!=0 && y<n) 
    	{
    		f[t].x=x;f[t].y=y+1;
    		t++;
    	}
    	if(a[x-1][y]!=0 &&  x>1) 
    	{
    		f[t].x=x-1;f[t].y=y;
    		t++;
    	}
    	if(a[x+1][y]!=0 && x<m) 
    	{
    		f[t].x=x+1;f[t].y=y;
    		t++;
    	}
    	if(a[x][y-1]!=0 &&  y>1) 
    	{
    		f[t].x=x;f[t].y=y-1;
    		t++;
    	}
    	return 0;
    }
    int main()
    {
    	int i,j,ans;
    	scanf("%d%d",&m,&n);
    	for(i=1;i<=m;i++)
    	{
    	  cin>>s;
    	  for(j=0;j<n;j++)
    	  {
    	  	 a[i][j+1]=s[j]-48;
    	  }
        }	    	
    	ans=0;
    	for(i=1;i<=m;i++)
    	{
    		for(j=1;j<=n;j++)
    		{
    			if(a[i][j]!=0)
    			{
    				h=1;t=1;l=1;
    			    f[t].x=i;f[t].y=j;
    			    t++;
    			    while(h<t)
    			    {
    			    	bfs(h);
    			    	h++;
    			    }
    			    ans++;
    		    }
    		}
    	}
    	cout<<ans<<endl;
    	return 0;
    }
    

    Pascal :

    var i,j,m,n,k:integer;
        a:array[-1..100,-1..100]of integer;
        b,c:array[0..10000]of integer;
        s:string;
        d1:array[1..4]of integer=(1,0,-1,0);
        d2:array[1..4]of integer=(0,1,0,-1);
    procedure work(x,y:integer);
    var i,j,h,l:integer;
    begin
      i:=x; j:=y; b[1]:=x; c[1]:=y; h:=2; l:=1; 
      while h>l do begin
        if a[b[l],c[l]]=0 then inc(l)
        else begin
          for i:=1 to 4 do begin
            b[h]:=b[l]+d1[i];
            c[h]:=c[l]+d2[i];
            inc(h);
          end;
          a[b[l],c[l]]:=0;
          inc(l);
        end;
      end;
      inc(k);
    end;
    begin
      fillchar(a,sizeof(a),0);
      readln(m,n);
      for i:=1 to m do begin
        readln(s);
        for j:=1 to n do begin
          if ord(s[j])-ord('0')>0 then a[i,j]:=1
          else a[i,j]:=0;
        end;
      end;
      k:=0;
      for i:=1 to m do for j:=1 to n do begin
        if a[i,j]>0 then work(i,j);
      end;
      write(k);
    end.
    
    
    • 1