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. }

複製代碼

若晴

1. #include <iostream>
   
2. #include<cstdlib>
   
3. using namespace std;
   
4. int main()
   
5. {
   
6.     int T;
   
7.     cin>>T;
   
8.     int N, M;
   
9.     cin>>N>>M;
   
10.     int wall = 0;
    
11.     char map[N][M];
    
12.     for(int i=0;i<N;i++)
    
13.     {
    
14.         for(int j=0;j<M;j++)
    
15.         {
    
16.             cin>>map[i][j];
    
17.         }
    
18.     }
    
19.     for(int i=0;i<N;i++)
    
20.     {
    
21.         for(int j=0;j<M;j++)
    
22.         {
    
23.             if(map[i][j]=='1')
    
24.             {
    
25.                 wall+=8;
    
26.             }
    
27.         }
    
28.     }
    
29.     for(int i=0;i<N;i++)
    
30.     {
    
31.         for(int j=0;j<M;j++)
    
32.         {
    
33.             if(map[i][j]=='1')
    
34.             {
    
35.                 if(map[i][j+1]=='1')
    
36.                 {
    
37.                     wall-=1;
    
38.                 }
    
39.                 if(map[i+1][j]=='1')
    
40.                 {
    
41.                     wall-=1;
    
42.                 }
    
43.                 if(map[i+1][j+1]=='1')
    
44.                 {
    
45.                     wall-=1;
    
46.                 }
    
47.                 if(map[i][j-1]=='1')
    
48.                 {
    
49.                     wall-=1;
    
50.                 }
    
51.                 if(map[i-1][j]=='1')
    
52.                 {
    
53.                     wall-=1;
    
54.                 }
    
55.                 if(map[i-1][j-1]=='1')
    
56.                 {
    
57.                     wall-=1;
    
58.                 }
    
59.                 if(map[i-1][j+1]=='1')
    
60.                 {
    
61.                     wall-=1;
    
62.                 }
    
63.                 if(map[i+1][j-1]=='1')
    
64.                 {
    
65.                     wall-=1;
    
66.                 }
    
67.                
    
68.             }
    
69.         }
    
70.     }
    
71.     cout<<wall;
    
72.     system("pause");
    
73.     return 0;
    
74. }

複製代碼