தீவு சுற்றளவு லீட்கோட் தீர்வு


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அமேசான் ப்ளூம்பெர்க் பேஸ்புக் கூகிள் மைக்ரோசாப்ட்
அணி

சிக்கல் அறிக்கை

இந்த சிக்கலில், எங்களுக்கு 2-டி வரிசை வடிவத்தில் ஒரு கட்டம் வழங்கப்படுகிறது. கட்டம் [i] [j] = 0 அந்த இடத்தில் நீர் இருப்பதைக் குறிக்கிறது மற்றும் கட்டம் [i] [j] = 1 நிலத்தை குறிக்கிறது. கட்டம் செல்கள் செங்குத்தாக / கிடைமட்டமாக இணைக்கப்பட்டுள்ளன, ஆனால் குறுக்காக இல்லை. கொடுக்கப்பட்ட உள்ளீட்டில் சரியாக ஒரு தீவு (நில கலங்களின் இணைக்கப்பட்ட கூறு) உள்ளது. இந்த சிக்கலின் சுற்றளவை நாம் தீர்மானிக்க வேண்டும்.

உதாரணமாக

grid = {{0,1,0,0},{1,1,1,0},{0,1,0,0},{1,1,0,0}}
16
grid = {{1}}
4

அணுகுமுறை (எளிய எண்ணுதல்)

சிக்கலைக் காண்பதற்கான எளிய வழி என்னவென்றால், நில செல்கள் மட்டுமே அளவுருவுக்கு பங்களிக்கும். சுற்றளவைக் கணக்கிடுவதற்கு வேறு எந்த நிலக் கலத்துடனும் பகிரப்படாத எந்தவொரு பக்கத்தையும் கொண்ட நிலக் கலத்தை கணக்கில் எடுத்துக்கொள்ளலாம். ஏனென்றால், ஒரு நிலக் கலமானது வேறு எந்த நிலக் கலத்துடனும் சில பக்கங்களைப் பகிர்ந்து கொண்டால், அது கட்டத்தில் தீவின் வெளிப்புற எல்லையாக இருக்காது.

தீவு சுற்றளவு லீட்கோட் தீர்வை செயல்படுத்துதல்

சி ++ திட்டம்

#include <bits/stdc++.h>

using namespace std;

int islandPerimeter(vector<vector<int>>& grid) {
    int n = grid.size() , m = grid[0].size();
    int perimeter = 0 , sides = 0;
    for(int i = 0 ; i < n ; i++)
        for(int j = 0 ; j < m;  j++) {
            if(grid[i][j] == 1) {
                sides = 0;
                if(i == 0)
                    sides++;
                else
                    sides += (grid[i - 1][j] == 0);

                if(j == 0)
                    sides++;
                else
                    sides += (grid[i][j - 1] == 0);

                if(i == n - 1)
                    sides++;
                else
                    sides += (grid[i + 1][j] == 0);

                if(j == m - 1)
                    sides++;
                else
                    sides += (grid[i][j + 1] == 0);

                perimeter += sides;
            }
        }
    return perimeter;
}

int main() {
    vector< vector <int> > grid = {{0 , 1 , 0 , 0},
                                   {1 , 1 , 1 , 0},
                                   {0 , 1 , 0 , 0},
                                   {1 , 1 , 0 , 0}};
    cout << islandPerimeter(grid) << endl;
    return 0;
}

ஜாவா திட்டம்

class island_perimeter {

    public static void main(String args[]) {
        int[][] grid = {{0 , 1 , 0 , 0},
                        {1 , 1 , 1 , 0},
                        {0 , 1 , 0 , 0},
                        {1 , 1 , 0 , 0}};
        System.out.println(islandPerimeter(grid));
    }

    public static int islandPerimeter(int[][] grid) {
        int n = grid.length , m = grid[0].length;
        int perimeter = 0 , sides = 0;
        for(int i = 0 ; i < n ; i++)
            for(int j = 0 ; j < m;  j++) {
                if(grid[i][j] == 1) {
                    sides = 0;
                    if(i == 0)
                        sides++;
                    else if(grid[i - 1][j] == 0)
                        sides++;

                    if(j == 0)
                        sides++;
                    else if(grid[i][j - 1] == 0)
                        sides++;

                    if(i == n - 1)
                        sides++;
                    else if(grid[i + 1][j] == 0)
                        sides++;

                    if(j == m - 1)
                        sides++;
                    else if(grid[i][j + 1] == 0)
                        sides++;

                    perimeter += sides;
                }
            }
        return perimeter;
    }
}
16

தீவு சுற்றளவு லீட்கோட் தீர்வின் சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (என் * எம்) கட்டத்தில் N = வரிசைகளின் எண்ணிக்கை, கட்டத்தில் M = நெடுவரிசைகளின் எண்ணிக்கை.

விண்வெளி சிக்கலானது 

ஓ (1) மாறிகளுக்கு நிலையான இடத்தைப் பயன்படுத்துவதால்.

அணுகுமுறை (பயனுள்ள எண்ணுதல்)

மேலே உள்ள அணுகுமுறையில், ஒரு நில கலத்தின் பக்கங்களை அதன் நான்கு அண்டை நாடுகளையும் சரிபார்த்து சுற்றளவுக்கு பங்களிப்பு செய்கிறோம். இரண்டு அயலவர்களைச் சரிபார்க்க அதை மேம்படுத்தலாம். அதைக் கடந்து செல்ல நாம் வலது மற்றும் கீழ் கட்டத்தில், இடது மற்றும் மேல் செல்களை ஒரு நில கலத்திற்கு மட்டுமே சரிபார்க்க முடியும். ஒவ்வொரு நில கலமும் தீவின் சுற்றளவுக்கு '4' பங்களிக்கிறது என்று நாம் கருதலாம். ஆனால் ஒரு நிலக் கலமானது அதன் பக்கத்தை (களை) வேறு எந்த கலத்துடன் பகிர்ந்து கொண்டால், அதிலிருந்து 2 ஐக் கழிப்போம் (ஒன்று அதன் பகிரப்பட்ட பக்கத்திற்கும் மற்றொன்று மற்ற கலமும் ஒரு பக்கத்தைப் பகிர்ந்து கொள்ளும்). இரண்டு தீர்வுகளின் நேர சிக்கலும் ஒன்றே ஆனால் இந்த அணுகுமுறையில் செயல்பாட்டின் அடிப்படையில் நாம் ஓரளவு மேம்படுகிறோம்.

தீவு சுற்றளவு லீட்கோட் தீர்வை செயல்படுத்துதல்

சி ++ திட்டம்

#include <bits/stdc++.h>

using namespace std;

int islandPerimeter(vector<vector<int>>& grid) {
    int n = grid.size() , m = grid[0].size() , perimeter = 0;
    for(int i = 0 ; i < n ; i++) {
        for(int j = 0 ; j < m ; j++) {
            if(grid[i][j] == 1) {
                perimeter += 4;

                if(i > 0 && grid[i - 1][j] == 1)
                    perimeter -= 2;

                if(j > 0 && grid[i][j - 1] == 1)
                    perimeter -= 2;
            }
        }
    }
    return perimeter;
}

int main() {
    vector< vector <int> > grid = {{0 , 1 , 0 , 0},
                                   {1 , 1 , 1 , 0},
                                   {0 , 1 , 0 , 0},
                                   {1 , 1 , 0 , 0}};
    cout << islandPerimeter(grid) << endl;
    return 0;
}

ஜாவா திட்டம்

class island_perimeter {

    public static void main(String args[]) {
        int[][] grid = {{0 , 1 , 0 , 0},
                        {1 , 1 , 1 , 0},
                        {0 , 1 , 0 , 0},
                        {1 , 1 , 0 , 0}};
        System.out.println(islandPerimeter(grid));
    }

    public static int islandPerimeter(int[][] grid) {
        int n = grid.length , m = grid[0].length , perimeter = 0;
        for(int i = 0 ; i < n ; i++) {
            for(int j = 0 ; j < m ; j++) {
                if(grid[i][j] == 1) {
                    perimeter += 4;

                    if(i > 0 && grid[i - 1][j] == 1)
                        perimeter -= 2;

                    if(j > 0 && grid[i][j - 1] == 1)
                        perimeter -= 2;
                }
            }
        }
        return perimeter;
    }
}
16

தீவு சுற்றளவு லீட்கோட் தீர்வின் சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (என் * எம்) கட்டத்தில் N = வரிசைகளின் எண்ணிக்கை, கட்டத்தில் M = நெடுவரிசைகளின் எண்ணிக்கை.

விண்வெளி சிக்கலானது 

ஓ (1) மாறிகளுக்கு நிலையான இடத்தைப் பயன்படுத்துவதால்.