npsc2010_B薑餅部落的危機

葉桔良

薑餅部落的危機
執行時間限制: 10 秒
薑餅部落位於遠得要命王國北方三千公里外，住民僅限於薑餅人一族。該部落散落於海上的島嶼群，由於終年冰雪籠罩因此海面常保持著結冰狀態。

以往薑餅人們和平地生活於此，但近年來溫室效應影響擴大造成極地暖化，使得薑餅人的性命受到威脅。(它們碰到水會立刻融化！！)有鑑於此，薑餅長老下令動員全部人力在所有陸地與海鄰接處築起高牆，以保護其家園不被海水侵蝕。不過薑餅人們的智慧並不高，無法計算需要的圍牆長度，請你寫一個程式幫助它們計算。

輸入檔說明
測資包含多組測試資料，第一列有一個整數 T 表示接下來有幾組測試資料。每組測試資料表示一張地圖，其第一列有兩個整數 N, M，代表該地圖的長與寬，地圖由 0 和 1 構成， 0 表示海面、 1 表示陸地，地圖外圍皆視同海面 (1 ≤ N, M ≤ 500)。

輸出檔說明
對每筆測試資料輸出隔絕海陸所需的圍牆長度。

範例輸入
2
4 5
00000
01010
01110
00000
4 5
00000
01110
01010
01100

範例輸出
12
16

葉桔良

1. #include <iostream>
   
2. using namespace std;
   
3. char grid[505][505];
   
4. 
   
5. int main() {
   
6.     int T, N, M;
   
7.     string s;
   
8.     cin >> T;
   
9.     while (T--){
   
10.         cin >> N >> M;
    
11.         for (int j = 0; j <= M+1; j++){
    
12.             grid[0][j] = '0'; //地圖外圍皆視同海面
    
13.         }
    
14.         for (int i = 1; i <= N; i++){
    
15.             cin >> s;
    
16.             grid[i][0] = '0'; //地圖外圍皆視同海面
    
17.             for (int j = 1; j <= M; j++){
    
18.                 grid[i][j] = s[j-1];
    
19.             }
    
20.             grid[i][M+1] = '0'; //地圖外圍皆視同海面
    
21.         }
    
22.         for (int j = 0; j <= M+1; j++){
    
23.             grid[N+1][j] = '0'; //地圖外圍皆視同海面
    
24.         }
    
25.         int ans = 0;
    
26.         for (int i = 0; i <= N; i++){
    
27.             for (int j = 0; j <= M; j++){
    
28.                 if (grid[i][j] != grid[i][j+1]){
    
29.                     ans++;
    
30.                 }
    
31.                 if (grid[i][j] != grid[i+1][j]){
    
32.                     ans++;
    
33.                 }
    
34.             }
    
35.         }
    
36.         cout << ans << "\n";
    
37.     }
    
38. }

複製代碼