Careercup

2014-05-02 00:22

原题：

Given a matrix consisting of 0's and 1's, find the largest connected component consisting of 1's.

题目：给定一个01矩阵，找出由1构成的连通分量中最大的一个。

解法：四邻接还是八邻接也不说，我就当四邻接了。这种Flood Fill问题，可以用BFS或者DFS解决。

代码：

 1 // http://www.careercup.com/question?id=5998719358992384
 2 #include <vector>
 3 using namespace std;
 4 
 5 class Solution {
 6 public:
 7     int maxConnectedComponent(vector<vector<int> > &v) {
 8         n = (int)v.size();
 9         if (n == 0) {
10             return 0;
11         }
12         m = (int)v[0].size();
13         if (m == 0) {
14             return 0;
15         }
16         
17         int res, max_res;
18         
19         max_res = 0;
20         for (i = 0; i < n; ++i) {
21             for (j = 0; j < m; ++j) {
22                 if (!v[i][j]) {
23                     continue;
24                 }
25                 res = 0;
26                 
27                 v[i][j] = 0;
28                 ++res;
29                 DFS(v, i, j, res);
30                 max_res = res > max_res ? res : max_res;
31             }
32         }
33         
34         return max_res;
35     };
36 private:
37     int n, m;
38     
39     void DFS(vector<vector<int> > &v, int i, int j, int &res) {
40         static const int d[4][2] = {
41             {-1,  0}, 
42             { 0, -1}, 
43             {+1,  0}, 
44             { 0, +1}
45         };
46         
47         int k, x, y;
48         for (k = 0; k < 4; ++k) {
49             x = i + d[k][0];
50             y = j + d[k][1];
51             if (x < 0 || x > n - 1 || y < 0 || y > m - 1) {
52                 continue;
53             }
54             if (!v[x][y]) {
55                 continue;
56             }
57             v[x][y] = 0;
58             ++res;
59             DFS(v, x, y, res);
60         }
61     };
62 };