最大联通子数组（结对开发）

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

要求：

文件读入数组。

结对开发的伙伴：

博客名：斗破2

姓名：王文奇

博客链接：http://www.cnblogs.com/qwer111/

分析：把二维数组看成一个个节点，使用深度优先遍历，递归遍历所有节点，设一个变量每访问一节点加上它的值，这个值与最大值比较，记录较大值，循环完后便是最大值。用文件输入流来读文件里存好的行列和数组。

代码：

  1 //最大子数组3   求一个二维数组的最大联通子数组
  2 //王文奇 缪金敏2016/4/4
  3 #include<iostream>
  4 #include<fstream>
  5 using namespace std;
  6 #define MAX 10000
  7 
  8 int row;
  9 int col;
 10 int Graph[MAX][MAX];
 11 bool v[MAX][MAX];
 12 int MaxSum;
 13 void BFS(int r, int c, int num)
 14 {
 15     if (MaxSum < num)
 16     {
 17         MaxSum = num;
 18         //v[r][c] = true;
 19     }
 20     if (r != (row - 1))
 21     {
 22         if (v[r + 1][c] == false)
 23         {
 24             v[r + 1][c] = true;
 25             BFS(r + 1, c, Graph[r + 1][c] + num);
 26             //if (Graph1[r + 1][c] == true)
 27             v[r + 1][c] = false;
 28         }
 29     }
 30     if (r != 0)
 31     {
 32         if (v[r - 1][c] == false)
 33         {
 34             v[r - 1][c] = true;
 35             BFS(r - 1, c, Graph[r - 1][c] + num);
 36             //if (Graph1[r - 1][c] == true)
 37             v[r - 1][c] = false;
 38         }
 39     }
 40     if (c != (col - 1))
 41     {
 42         if (v[r][c + 1] == false)
 43         {
 44             v[r][c + 1] = true;
 45             BFS(r, c + 1, Graph[r][c + 1] + num);
 46             //if (Graph1[r][c + 1] == true)
 47             v[r][c + 1] = false;
 48         }
 49     }
 50     if (c != 0)
 51     {
 52         if (v[r][c - 1] == false)
 53         {
 54             v[r][c - 1] = true;
 55             BFS(r, c - 1, Graph[r][c - 1] + num);
 56             //if (Graph1[r][c-1] == true)
 57             v[r][c - 1] = false;
 58         }
 59     }
 60 }
 61 
 62 int main()
 63 {
 64     MaxSum = 0;
 65     char a[20];
 66     cout << "请输入要读入的文件名与地址(如：D:\test.txt)：";
 67     cin >> a;
 68     ifstream infile;
 69     infile.open(a, ios::in);
 70     if (infile.is_open() == false)
 71     {
 72         cerr << "open error!" << endl;
 73         exit(1);
 74     }
 75 
 76 //    cout << "请分别输入二维数组的行数和列数：";
 77     infile >> row;
 78     infile >> col;
 79 //    cin >> row >> col;
 80 //    cout << "请输入二维数组数据：
";
 81     for (int i = 0; i < row; i++)
 82     {
 83         for (int j = 0; j < col; j++)
 84         {
 85             infile >> Graph[i][j];
 86         }
 87     }
 88     for (int i = 0; i < row; i++)
 89     {
 90         for (int j = 0; j < col; j++)
 91         {
 92             v[i][j] = false;
 93         }
 94     }
 95     for (int i = 0; i < row; i++)
 96     {
 97         for (int j = 0; j < col; j++)
 98         {
 99             v[i][j] = true;
100             BFS(i, j, Graph[i][j]);
101             v[i][j] = false;
102         }
103     }
104 
105     cout << "二维数组：
";
106     for (int i = 0; i < row; i++)
107     {
108         for (int j = 0; j < col; j++)
109         {
110             cout<< Graph[i][j]<<" ";
111         }
112         cout << endl;
113     }
114     cout << "最大联通子数组的和：";
115     cout << MaxSum<<endl;
116     infile.close();
117     return 0;
118 }

运行结果截图：

总结：

这次程序在前一次的矩阵子数组要求下加了一个子数组链路，相对比较难，要获得联通子数组就要求遍历节点，所以我考虑到了深度优先遍历。

项目计划总结：

时间记录日志：

缺陷记录日志：