摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

範例輸入:

10 10
0 1 0 0 0 0 0 1 0 0
1 1 1 0 0 0 1 1 0 0
0 1 0 0 0 0 1 1 1 0
0 0 1 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0

3 2
1 1
0 1
1 0

範例輸出:

6 8 10
4

/********************************************************/

#include<stdio.h>
#include<stdlib.h>
main()
{
  int N,M,a,b,c;
   while(scanf("%d %d",&N,&M)==2)
       {
          int MAP[101][101]={0};
          for(a=1;a<=N;a++)
             for(b=1;b<=M;b++)
                scanf("%d",&MAP[a][b]);
          int D[9][2]={
                        {1,0},{-1,0},
                        {0,1},{1,1},{-1,1},
                        {-1,-1},{0,-1},{1,-1}    
                        };//檢查的方位
          for(a=1;a<=N;a++) 
             for(b=1;b<=M;b++) //找一個做起頭
                if(MAP[a][b]==1)
                  {
                    MAP[a][b]=0; //利用BFS擴散找區域數
                    int Queue[10001][0],top=0,E=0;
                    Queue[0][0]=a,Queue[0][1]=b;
                    for(E=0;E<=top;E++)
                       {
                          int x=Queue[E][0],y=Queue[E][1];
                          for(c=0;c<8;c++) //將八周的點丟入佇列
                             if(MAP[x+D[c][0]][y+D[c][1]]==1)
                               {
                                  MAP[x+D[c][0]][y+D[c][1]]=0;
                                  ++top;
                                  Queue[top][0]=x+D[c][0];
                                  Queue[top][1]=y+D[c][1];
                               }
                       }
                       printf("%d ",top+1); //輸出該區域的數量
                  }
             puts("");
       }
    return 0;
}