返回一个二维整数数组中最大联通子数组的和

浏览数：13 / 时间：2015年06月11日

设计思路：

首先将二维数组中正整数的值找出来，之后找到每个正整数上下左右加起来为正的负数。之后判断是否联通，将小的负数排除掉，最后留下的是二维整数数组中最大联通子数组。

程序代码：

  1 #include <iostream>
  2 #include <time.h>
  3 #define M 3
  4 #define N 5
  5 using namespace std;
  6 
  7 void main()
  8 {
  9     int a[M][N] = {0},b[M][N]={0};//判断联通性，0为未选中，1为选中,2为连通
 10     bool flg = 0; //判断是否有1存在，存在为O。
 11     int sum = 0; //最后和
 12 
 13     srand(unsigned((int)time(0)));
 14     for (int i = 0;i < M;i++)
 15     {
 16         for (int j = 0;j < N;j++)
 17         {
 18             a[i][j] = rand()%50 - 20;
 19             cout << a[i][j] << "\t";
 20             if (a[i][j] >= 0)
 21             {
 22                 b[i][j] = 1;
 23             }
 24         }
 25         cout << endl;
 26     }
 27     cout << endl;
 28         
 29     for (int i = 0;i < M;i++)
 30     {
 31         for (int j = 0;j < N;j++)
 32         {
 33             if (b[i][j] == 1)
 34             {
 35                 if (a[i+1][j] + a[i][j] > 0 && b[i+1][j] == 0)
 36                 {
 37                     b[i+1][j] = 2;                            
 38                 }
 39                 if (a[i-1][j] + a[i][j] > 0 && b[i-1][j] == 0)
 40                 {
 41                     b[i-1][j] = 2;    
 42                 }
 43                 if (a[i][j-1] + a[i][j] > 0 && b[i][j-1] == 0)
 44                 {
 45                      b[i][j-1] = 2;        
 46                 }
 47                 if (a[i][j+1] + a[i][j] > 0 && b[i][j+1] == 0)
 48                 {
 49                     b[i][j+1] = 2;    
 50                 }                  
 51             }                        
 52         }
 53     }
 54 
 55     for (int i = 0;i < M;i++)
 56     {
 57         for (int j = 0;j < N;j++)
 58         {                
 59             flg = 0;
 60             if (b[i][j] != 0 && a[i][j] < 0)
 61             {
 62                 b[i][j] = 0;
 63                 for (int k = 0;k < M;k++)
 64                 {
 65                     for (int l = 0;l < N;l++)
 66                     {
 67                         if (b[k][l] != 0)
 68                         {
 69                             if ((b[k+1][l] <= 0 || b[k+1][l] > 2)&&
 70                                 (b[k-1][l] <= 0 || b[k-1][l] > 2)&&
 71                                 (b[k][l+1] <= 0 || b[k][l+1] > 2)&&
 72                                 (b[k][l-1] <= 0 || b[k][l-1] > 2))
 73                             {
 74                                 flg = 1;
 75                             }
 76                         }                                
 77                     }
 78                 }
 79                 if (flg)
 80                 {
 81                     b[i][j] = 2;
 82                 }                        
 83             }
 84         }
 85     }
 86 
 87     for (int i = 0;i < M;i++)
 88     {
 89         for (int j = 0;j < N;j++)
 90         {
 91             if (b[i][j] != 0)
 92             {
 93                 cout << a[i][j] << "\t";
 94                 sum += a[i][j];
 95             }
 96             else
 97             {
 98                 cout << "**" << "\t";
 99             }
100         }
101         cout << endl;
102     }
103     
104     cout << "sum = " << sum << endl;
105 }