声明：原题目转载自中山大学sicily平台，解答部分为原创
Problem ：
对于一个01矩阵A，求其中有多少片连成一片的1. 每个1可以和上下左右的1相连.
请为下面的Solution类实现解决这一问题的函数countConnectedOnes，函数参数A为给出的01矩阵，A的行数和列数均不大于1000. 函数的返回值是问题的答案.
int countConnectedOnes(vector<vector<char>>& A) {
例1： 例2：
A = B =
100 1101
010 0101
001 1110
答案为3. 答案为2
Solution：
思路：递归问题。假定移动的路线都存放在一个栈空间里面。当移动到某一行某一列时，如果选到了“1”并识别该位置“未操作过”，则对该位置进行操作，并将上下左右四个位置压入栈中，再移动到该栈的下一个位置，重复以上操作直至栈空间为空。
以下代码是使用数组实现的方式：
class Solution {
public:
int countConnectedOnes(vector<vector<char> >& A) {
if(A.size() == 0 || A[0].size() == 0)
return 0;
int count = 0;
for(int i = 0; i < A.size() ; i ++)
{
for(int j = 0; j < A[0].size(); j ++)
{
if(A[i][j] == '1')
{
count ++;
change(i, j, A);
}
}
}
return count;
}
private:
void change(int row, int col, vector<vector<char> >& A)
{
if(A[row][col] == '0')
return;
if(A[row][col] == '1')
{
A[row][col] = 'x';
if(row - 1 >= 0)
change(row - 1, col, A);
if(row + 1 < A.size())
change(row + 1, col, A);
if(col - 1 >= 0)
change(row, col - 1, A);
if(col + 1 < A[0].size())
change(row, col + 1, A);
}
}
};
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
