1 条题解

  • 0
    @ 2025-2-14 21:23:51

    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<cstring>
    using namespace std;
    int n,m,tot=0;
    char a[101][101];
    int dx[]={0,-1,0,1},dy[]={-1,0,1,0};
    bool b[101][101];
    struct data{
    	int x,y;
    }p[1000];
    void dfs(int r,int s)
    {
    	int head,tail;
    	int nx,ny,first=1;
    	
    	head=1;tail=1;
    	p[head].x=r;
    	p[head].y=s;
    	b[r][s]=false;
    	++tot;
    	while(head<=tail)
    	{
    		
    		for(int i=0;i<4;++i)
    		{
    		    nx = p[head].x+dx[i];
    			ny = p[head].y+dy[i];
    			
    			if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&b[nx][ny]==true)
    			{
    				++tail;
    				p[tail].x=nx;
    				p[tail].y=ny;
    				b[nx][ny]=false;
    			}
    			/*if(head==tail)
    			{
    				
    				for(int i=1;i<=n;++i)
    				{
    					for(int j=1;j<=m;++j)
    					 cout << b[i][j] << " ";
    					cout << endl;
    				}
    				cout << endl;
    				return;
    			}*/
    		}
    		++head;
    	}
    }
    int main()
    {
    	cin >> n >> m;
    	
    	for(int i = 1; i <= n ;++i)
    	for(int j = 1;j <= m; ++j)
    	 {
    	   cin >> a[i][j];
    	   
    	   if(int(a[i][j]-48))b[i][j]=true;
    	   else b[i][j]=false;
         }
    	
    	for(int i=1;i<=n;++i)
    	for(int j=1;j<=m;++j)
    	{
    		if(b[i][j])
    		dfs(i,j);
    	}
    	
    	cout << tot;
    	
    	return 0;
    }
    

    Pascal :

    const dx:array[1..4] of -1..1=(-1,0,1,0);
    dy:array[1..4] of -1..1=(0,1,0,-1);
    var int:text;
    name,s:string;
    pic:array[1..50,1..79] of byte;
    bz:array[1..50,1..79] of boolean;
    m,n,i,j,num:integer;
    h:array[1..4000,1..2] of byte;
    procedure doing(p,q:integer);
    var i,t,w,x,y:integer;
    begin
    inc(num);bz[p,q]:=false;
    t:=1;w:=1;h[1,1]:=p;h[1,2]:=q;
    repeat
    for i:=1 to 4 do
    begin
    x:=h[t,1]+dx[i];
    y:=h[t,2]+dy[i];
    if (x>0) and (x<=m) and (y>0) and (y<=n) and bz[x,y]
    then begin
    inc(w);h[w,1]:=x;
    h[w,2]:=y;bz[x,y]:=false;end;
    end;
    inc(t);
    until t>w;
    end;
    begin
    fillchar(bz,sizeof(bz),true);num:=0;
    readln(m,n);
    for i:=1 to m do
    begin readln(s);
    for j:=1 to n do
    begin pic[i,j]:=ord(s[j])-ord('0');
    if pic[i,j]=0 then bz[i,j]:=false;
    end;
    end;
    for i:=1 to m do
    for j:=1 to n do if bz[i,j] then doing(i,j);
    writeln(num);
    readln;
    end.
    
    

    Java :

    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Scanner;
    
    public class Main {
    	static int [][] map;
    	static int n,m,count = 0;
    	public static void main(String[] agrs) {
    		Scanner cin = new Scanner(System.in);
    		n = cin.nextInt();
    		m = cin.nextInt();
    		cin.nextLine();
    		map = new int[n][m];
    		for(int i = 0; i < n; i ++) {
    			String str = cin.nextLine();
    			for(int j = 0; j < m; j ++) 
    				map[i][j] = Integer.parseInt(str.substring(j, j+1));
    		}
    		
    		for(int i = 0; i < n; i ++) {
    			for(int j = 0; j < m; j ++) {
    				if(map[i][j]!=0) {
    					bfs(i,j);
    					count ++;
    				}
    			}
    		}
    		System.out.println(count);
    	}
    
    	public static void bfs(int x,int y) {
    		int [] dx= {0,-1,0,1};
    		int [] dy = {-1,0,1,0};		
    		map[x][y] = 0;
    		for(int i = 0; i < 4; i ++) {
    			int tx = x + dx[i];
    			int ty = y + dy[i];
    			if(tx >= 0 && tx < n && ty >= 0 && ty < m && map[tx][ty] != 0) {
    				bfs(tx,ty);
    			}
    		}
    	}
    }
    
    • 1

    信息

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