C++筆記 島嶼計算


題目

在遠的要命王國,有一位國王在清點國家的領地數量,然而領地實在是太分散了,國王難以確實清點,請你幫助國王清點國家的領地數量 。
程式說明:
程式的輸入分為兩個部分,第一部分為地圖大小,輸入兩個整數分別為地圖的列數與行數,第二部分為地圖本體,由0與1組成,0為海洋、1為陸地,如下
4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
輸出為地圖上分離的陸地數量,如下:
3

補充說明:

  1. 地圖大小不會超過10 * 10
  2. 注意輸出最後須用endl換行

完整程式碼

#include<iostream>
using namespace std;
//1. import the lib
#include<string>
#include<vector>

//https://husking-studio.com/cpp-pass-2d-array-as-function-parameter/


//5.把連通的陸地都走過變成0 (遞迴)
void goAround(int* world, int r, int c,int row,int column){

    //world[r][c]的位置記為now
    int* now = world+c+column*r;

    //踩過的陸地計為0
    *(now)=0;

    //取得now上下左右數值(1 or 0)
    int top = *(now-column);
    int down = *(now+column);
    int left = *(now-1);
    int right = *(now+1);

    //得知now是否有上下左右(陣列邊界元素可能就不會有/上/下/左/右)
    bool hastop = (r>0)?true:false;
    bool hasdown = (r<row-1)?true:false;
    bool hasleft = (c>0)?true:false;
    bool hasright = (c<column-1)?true:false;

    //接者now的上下左右去逛一遍

    //top
    if( hastop && top==1) goAround(world,r-1,c,row,column);
    //down
    if( hasdown && down==1) goAround(world,r+1,c,row,column);
    //left
    if( hasleft && left==1) goAround(world,r,c-1,row,column);
    //right
    if( hasright && right==1) goAround(world,r,c+1,row,column);
}


int main(){

    //1.輸入地圖的大小
    int row;
    int column;
    cin >> row >> column;

    //2.初始化地圖
    int world[row][column];

    //3.輸入陸地、海洋
    for(int r=0;r<row;r++){
        for(int c=0;c<column;c++){
            int set;
            cin >> set;
            world[r][c]=set;
        }
    }

    //4.計算陸地塊數

   //計連通陸地的數量
    int land = 0;

    //針對地圖的每一點workd[i][j]看可不可以走,是1才可以走
    //踩world[i][j]的每個點,如果是1就把那塊陸地相連的部分走完,是0就直接看下一個world[i][j]點
    for(int r=0;r<row;r++){
        for(int c=0;c<column;c++){
            if(world[r][c]==1){
                //5. function 把world[r][c]附近的陸地巡過一遍
                goAround((int*)world,r,c,row,column);
                land++;
            }
        }
    }

    cout << land << endl ;

    return 0;
}

解題觀念及思路








你可能感興趣的文章

pygame 開發之打磚塊遊戲

pygame 開發之打磚塊遊戲

W13_作業一實作記錄

W13_作業一實作記錄

Web 資訊安全(Security)簡明入門教學指南

Web 資訊安全(Security)簡明入門教學指南






留言討論