[C_CH13-中] 坑洞路面(C++)

[C_CH13-中] 坑洞路面

問題描述 ：
有一個路段因為砂石車經常行駛導致路面坑坑洞洞，由於路面坑洞的關係，下雨天之後就顯得越來越容易積水了，某天雨後，大華想到路面上觀察坑洞裡的積水，並算出積水量。輸入為路面的高低起伏值，輸出為積水量。例如右圖，灰色地方為路面的高低起伏，高度分別為3 2 1 4 2 3 5，藍色部分為積水的區域。

輸入說明 ：
第一列輸入為一個正整數N，代表計算的路面寬度有N個單位。
第二列輸入為N個正整數，代表路面的高低起伏。
輸出說明 ：
輸出為一個正整數，代表積水的區域有多少。
範例 ：

Sample Input:	Sample Output:
7 3 2 1 4 2 3 5	6

說明:

N = 7

3 2 1 4 2 3 5

1.將路面初始化

0	0	0	0	0	0	0
0	0	0	0	0	0	0
0	0	0	0	0	0	0
0	0	0	0	0	0	0
0	0	0	0	0	0	0

2.將路面高度設為1

0	0	0	0	0	0	1
0	0	0	1	0	0	1
1	0	0	1	0	1	1
1	1	0	1	1	1	1
1	1	1	1	1	1	1

3.接著用陣列一列一列的尋找，計算兩個1之間0的數量，就是會積水的地方

第一列

0	0	0	0	0	0	1
0	0	0	1	0	0	1
1	0	0	1	0	1	1
1	1	0	1	1	1	1
1	1	1	1	1	1	1

第二列

計算兩個1(粗體字)之間，0的數量

首先要記住第一個1的位置(位置是3)，接著找第二個1(位置是6)

第二個位置 - 第一個位置 - 1 = 0的數量(2)

0	0	0	0	0	0	1
0	0	0	1	0	0	1
1	0	0	1	0	1	1
1	1	0	1	1	1	1
1	1	1	1	1	1	1

第三列

首先要記住第一個1的位置(位置是0)，接著找第二個1(位置是3)

第二個位置 - 第一個位置 - 1 = 0的數量(2)

接著把第二個1的位置當成新的第一個1的位置(位置是3)

找新的第二個1(位置是5)

新第二個位置 - 新第一個位置 - 1 = 0的數量(1)

0	0	0	0	0	0	1
0	0	0	1	0	0	1
1	0	0	1	0	1	1
1	1	0	1	1	1	1
1	1	1	1	1	1	1

以此類推，在過程中把計算到0的數量加起來，就是水坑的數量了。

1. #include <iostream>  
2. using namespace std;  
3.   
4. int main() {  
5.     // [C_CH13-中] 坑洞路面  
6.     int N;  
7.     cin >> N;  
8.     int num[N];  
9.     int max = -1;  
10.     //使用者輸入並找出最高的路  
11.     for(int i = 0;i < N;i++)  
12.     {  
13.         cin >> num[i];      
14.         if(num[i] > max)  
15.         {  
16.             max = num[i];  
17.         }  
18.     }  
19.     //用二維陣列建立路面圖，初始化  
20.     int road[max][N];  
21.     for(int i = 0;i < max;i++)  
22.     {  
23.         for(int j = 0;j < N;j++)  
24.         {  
25.             road[i][j] = 0;  
26.         }  
27.     }  
28.     int c = 0;  
29.     //用二維陣列建立路面圖  
30.     for(int i = 0;i < max;i++)  
31.     {  
32.         for(int j = 0;j < N;j++)  
33.         {  
34.             if(i+num[j] >= max)  
35.             {  
36.                 road[i][j] = 1;  
37.             }  
38.         }  
39.     }  
40.       
41.     //計算凹洞數  
42.     int fpos;  
43.     int result = 0;  
44.     bool fir = false;//沒有第一個1  
45.     for(int i = 0;i < max;i++)  
46.     {  
47.         for(int j = 0;j < N;j++)  
48.         {  
49.             if(road[i][j] == 1)  
50.             {  
51.                 if(fir == false)  
52.                 {  
53.                     fpos = j;  
54.                     fir = true;  
55.                 }  
56.                 else  
57.                 {  
58.                     result = result + (j-fpos-1);  
59.                     fpos = j;  
60.                 }  
61.             }  
62.         }  
63.         fir = false;  
64.     }  
65.     cout << result << endl;  
66.     return 0;  
67. }