Yahoo : Find number of black regions in a plane

Given a white background with a black random shape scattering around. Describe and
code an algorithm to count the number of
black shapes. You can assume input to be an array of 3xMxN in RGB color space.

简单题 ...

回复 1# wwwyhx
输入是3维？看题意像是求黑色的联通分量的个数？如果是这样就DFS或BFS就行了吧

就是递归+记录pass过的

1. 
   
2. void ClearConnected(int** pPlane, int m, int n, int x, int y)
   
3. {
   
4.         assert(pPlane && m > 0 && n > 0);
   
5. 
   
6.         if (x < 0 || x >= m) return;
   
7.         if (y < 0 || y >= n) return;
   
8. 
   
9.         if (0 == pPlane[x][y])
   
10.                 return;
    
11. 
    
12.         if (1 == pPlane[x][y])
    
13.                 pPlane[x][y] = 0;
    
14. 
    
15.         ClearConnected(pPlane, m, n, x+1, y);
    
16.         ClearConnected(pPlane, m, n, x-1, y);
    
17.         ClearConnected(pPlane, m, n, x, y+1);
    
18.         ClearConnected(pPlane, m, n, x, y-1);
    
19.         ClearConnected(pPlane, m, n, x-1, y+1);
    
20.         ClearConnected(pPlane, m, n, x+1, y+1);
    
21.         ClearConnected(pPlane, m, n, x-1, y-1);
    
22.         ClearConnected(pPlane, m, n, x+1, y-1);
    
23. }
    
24. 
    
25. int CountBlackRegions(int** pPlane, int m, int n)
    
26. {
    
27.         assert(pPlane && m > 0 && n > 0);
    
28. 
    
29.         int nCount = 0;
    
30.         for (int i = 0; i < m; i++)
    
31.                 for (int j = 0; j < n; j++)
    
32.                 {
    
33.                         if (1 == pPlane[i][j])
    
34.                         {
    
35.                                 nCount++;
    
36.                                 ClearConnected(pPlane, m, n, i, j);
    
37.                         }
    
38.                 }
    
39. 
    
40.                 return nCount;
    
41. }
    

复制代码