问题描述

C:岛屿面积总时间限制: 1000ms 内存限制: 65536kB 描述用一个nm的二维数组表示地图，1表示陆地，0代表海水，每一格都表示一个11的区域。地图中的格子只能横向或者纵向连接（不能对角连接），连接在一起的陆地称作岛屿，同时整个地图都被海水围绕。假设给出的地图中只会有一个岛屿，并且岛屿中不会有湖（即不会有水被陆地包围的情况出现）。请判断所给定的二维地图中岛屿的周长。

输入第一行为n和m，表示地图的大小(1<=n<=100, 1<=m<=100)。接下来n行，每行有m个数，分别描述每一格的数值。数值之间均用空格隔开。输出只有一行，即岛屿的周长（正整数）。样例输入 3 4 1 1 1 0 0 1 0 0 1 1 0 0 样例输出 14

解决方案

#include<iostream>
#include<cmath>
#include<string>
#include<iterator>

using namespace std;

int main(){
    // get input
    int r,c;
    cin >> r >> c;
    int **pr = new int*[r];
    for(int i=0;i<r;i++){
        pr[i] = new int[c];
    }
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            cin >> pr[i][j];
        }
    }

    /* test input
        int pr[3][4] = { {1,1,1,0},
                      　{0,1,0,0},
                      　{1,1,0,0} };
    */

    // calculate c
    int tot = 0;
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            if(pr[i][j]==0) continue;
            if((j-1>=0 && !pr[i][j-1])
                    || (j-1<0))  tot++;
            if((j+1<c && !pr[i][j+1])
                    || (j+1>=c))  tot++;
            if((i-1>=0 && !pr[i-1][j])
                    || (i-1<0)) tot++;
            if((i+1<r && !pr[i+1][j])
                    || (i+1>=r))  tot++;
        }
    }

    // delete space
    for(int i=0;i<r;i++){
        delete[] pr[i];
    }
    cout << tot << endl;
    return 0;
}

知识点以及优化

可以写测试，避免手动重复输入数值

可以初始化一个全０的很大的二维数组，并令坐标从１开始，简化判断条件

 for(i=1;i<=n;i++){
     for(j=1;j<=m;j++){
         if(a[i][j]==1){
             cnt=cnt+4-(a[i-1][j]+a[i+1][j]+a[i][j-1]+a[i][j+1]);
         }
     }
 }

oj-岛屿问题

问题描述

解决方案

知识点以及优化

Similar Posts

Comments