Careercup - Facebook面试题 - 5998719358992384

2014-05-02 00:22

题目链接

原题：

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

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

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

代码：

 // http://www.careercup.com/question?id=5998719358992384

 #include <vector>

 using namespace std;

 class Solution {

 public:

     int maxConnectedComponent(vector<vector<int> > &v) {

         n = (int)v.size();

         if (n == ) {

             return ;

         }

         m = (int)v[].size();

         if (m == ) {

             return ;

         }

         int res, max_res;

         max_res = ;

         for (i = ; i < n; ++i) {

             for (j = ; j < m; ++j) {

                 if (!v[i][j]) {

                     continue;

                 }

                 res = ;

                 v[i][j] = ;

                 ++res;

                 DFS(v, i, j, res);

                 max_res = res > max_res ? res : max_res;

             }

         }

         return max_res;

     };

 private:

     int n, m;

     void DFS(vector<vector<int> > &v, int i, int j, int &res) {

         static const int d[][] = {

             {-,  },

             { , -},

             {+,  },

             { , +}

         };

         int k, x, y;

         for (k = ; k < ; ++k) {

             x = i + d[k][];

             y = j + d[k][];

             if (x <  || x > n -  || y <  || y > m - ) {

                 continue;

             }

             if (!v[x][y]) {

                 continue;

             }

             v[x][y] = ;

             ++res;

             DFS(v, x, y, res);

         }

     };

 };