題目:傳回一個二維整數數組中最大聯通子數組的和。
要求：
檔案讀入數組。
結對開發的夥伴：
部落格名：Mr.缪
姓名：缪金敏
連結：http://www.cnblogs.com/miaojinmin799/
分析：把二維數組看成一個個節點，使用深度優先周遊，遞歸周遊所有節點，設一個變量每通路一節點加上它的值，這個值與最大值比較，記錄較大值，循環完後便是最大值。用檔案輸入流來讀檔案裡存好的行列和數組。
代碼：
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 << "請輸入二維數組資料：\n";
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 << "二維數組：\n";
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 } 運作結果截圖：
總結：
這次的題目比較難，借助了資料結構裡深度優先周遊的算法。
項目計劃總結：
時間記錄日志：
缺陷記錄日志：