ओ (आर * सी) पर बिटमैप में संगत क्षेत्रों की गणना कर सकते हैं?

Question

आपको उपग्रह द्वारा चित्रित सतह की एक छवि दी गई है। छवि एक बिटमैप है जहां पानी को '।' द्वारा चिह्नित किया जाता है। और भूमि को * 'द्वारा चिह्नित किया गया है। '* के एक समूह का एक समूह है। (दो '*' क्षैतिज, ऊर्ध्वाधर या विकर्ण पड़ोसियों के निकट हैं)। आपका काम बिटमैप में द्वीपों की संख्या मुद्रित करना है।

उदाहरण इनपुट: -

.........** 
**......*** 
........... 
...*....... 
*........*. 
*.........* 

आउटपुट: - 5

यहाँ, मेरी कार्यान्वयन जो O(r * c) अंतरिक्ष और O(r * c) अंतरिक्ष आर कुल नहीं है जहां लेता है। पंक्तियों और सी का कुल योग नहीं है।

#include <stdio.h> 
#define COLS 12 

void markVisted(char map[][COLS], int visited[][COLS], int row, int col, int rowCount) 
{ 
    if((row < 0) || (row >= rowCount) || (col < 0) || (col >= COLS) || (map[row][col] != '*') || (visited[row][col] == 1)) return; 

    visited[row][col] = 1; 

    //calling neighbours 
    markVisted(map, visited, row+1, col, rowCount); 
    markVisted(map, visited, row, col+1, rowCount); 
    markVisted(map, visited, row-1, col, rowCount); 
    markVisted(map, visited, row, col-1, rowCount); 
    markVisted(map, visited, row+1, col+1, rowCount); 
    markVisted(map, visited, row-1, col-1, rowCount); 
    markVisted(map, visited, row-1, col+1, rowCount); 
    markVisted(map, visited, row+1, col-1, rowCount); 
} 
int countIslands(char map[][COLS], int visited[][COLS], int rowCount) 
{ 
    int i, j, count = 0; 
    for(i=0; i<rowCount; ++i){ 
     for(j=0; j<COLS; ++j){ 

      if((map[i][j] == '*') && (visited[i][j] == 0)){ 
       ++count; 
       markVisted(map, visited, i, j, rowCount); 
      } 
     } 
    } 
    return count; 
} 

int main() 
{ 
    char map[][COLS] = { 
        "*..........", 
        "**........*", 
        "...........", 
        "...*.......", 
        "*........*.", 
        "..........*"    
        }; 
    int rows = sizeof(map)/sizeof(map[0]); 
    int visited[rows][COLS], i, j; 

    for(i=0; i<rows; ++i){ 
     for(j=0; j<COLS; ++j) visited[i][j] = 0; 
    } 

    printf("No. of islands = %d\n", countIslands(map, visited, rows)); 


    return 0; 
} 

इस समस्या
भी सुझावों को बेहतर बनाने के लिए अपने समाधान का स्वागत किया है के लिए कुछ बेहतर तर्क का सुझाव दें।

Answer 1

मुझे लगता है कि यहां भ्रम यह है कि आपका एल्गोरिदम वास्तव में रैखिक समय में चलता है, समयबद्ध नहीं।

बड़े-ओ नोटेशन का उपयोग करते समय, n इनपुट आकार के लिए खड़ा है। आपका इनपुट यहां सिर्फ r या सिर्फ c है, बल्कि r * c, क्योंकि यह नोड्स का ग्रिड है। आपके एल्गोरिदम O(r * c) में चलता है, जैसा कि आपने अपने प्रश्न में कहा था ... इस प्रकार आपका एल्गोरिदम O(n) में चलता है जो रैखिक समय है।

ऐसा लगता है कि इस समस्या को हल करने वाले किसी भी एल्गोरिदम को सबसे खराब मामले में एक बार प्रत्येक इनपुट सेल को पढ़ना होगा। इस प्रकार सबसे अच्छा चलने वाला समय आप O(n) के लिए उम्मीद कर सकते हैं। चूंकि आपका एल्गोरिदम O(n) में चलता है, इसलिए आपके पास प्रस्तावित एल्गोरिदम की तुलना में किसी भी एल्गोरिदम नहीं होता है जो सबसे तेज़ मामले में तेज़ क्रम का चलता है।

मैं कुछ चालाक चाल के बारे में सोच सकता हूं। उदाहरण के लिए, यदि आपके पास * एस का ब्लॉक है, तो आप कुछ मामलों में केवल विकर्णों की जांच कर सकते हैं।यही कारण है, अगर आप

...... 
.****. 
.****. 
.****. 
.****. 
...... 

है इससे कोई फर्क नहीं होगा यदि आप केवल इन कोशिकाओं पढ़ें:

जब तक

...... 
.*.*.. 
..*.*. 
.*.*.. 
..*.*. 
...... 

उदाहरण के लिए आप नीचे बाईं ओर सबसे कोने में कुछ, जिस स्थिति में है आपको उस निचले बाएं-सबसे अधिक * को पढ़ने की आवश्यकता होगी। तो शायद कुछ मामलों में आपका एल्गोरिदम अधिक तेज़ी से चला सकता है, लेकिन सबसे खराब मामले (जो O उपायों के लिए है) के लिए, यह O(n) होना चाहिए।

संपादित करें: यहां तक ​​कि उस मामले में जहां आप केवल आधे नोड्स पढ़ते हैं, रन-टाइम O(n/2) होगा जो अभी भी एक ही ऑर्डर (O(n)) है।

Answer 2

यह connected component labeling से अत्यधिक संबंधित है। कनेक्टेड घटक की संख्या केवल लेबलिंग का एक उपज है। जुड़े विकिपीडिया लेख में वर्णित एल्गोरिदम रैखिक समय में काम करता है।

Answer 3

1. एक अप्रत्यक्ष ग्राफ बनाएं, जहां प्रत्येक द्वीप नोड अपने पड़ोसी द्वीप नोड्स से जुड़ता है।

2. जबकि वहाँ विज़िट नहीं किए गए नोड्स हैं:

   • एक विज़िट नहीं किए गए नोड लेने, गहराई-प्रथम ट्रेवर्सल करते हैं और का दौरा किया, number_of_islands वृद्धि प्रत्येक नोड निशान।

3. हो गया।

दोनों (1) और (2) ओ (एन) समय लेते हैं।

Answer 4

द्वीपों की प्रकृति के बारे में किसी भी apriori ज्ञान के बिना एल्गोरिदम को समय में ओ (एन) से अधिक कुशल नहीं बनाया जा सकता है, हालांकि स्मृति के अनुसार आपके अलगो में सुधार किया जा सकता है। देखी गई सरणी बस अनावश्यक है।

#include <stdio.h> 
#define COLS 12 


int main() 
{ 
    char map[][COLS] = { 
      "*..........", 
      "**........*", 
      "...........", 
      "...*.......", 
      "*........*.", 
      "..........*"    
      }; 
    int rows = sizeof(map)/sizeof(map[0]); 
    int i, j; 

    int main_count = 0; 

    if(map[0][0] == '*') { 
     main_count++; 
    } 
    for(j=0; j<COLS-1; j++) { 
     if((map[0][j]-map[0][j+1])==4) { 
      main_count++; 
     } 
    } 

    for(i=1; i<rows; ++i){ 
     if(map[i][0] == '*' && (map[i][0]-map[i-1][0]-map[i-1][1])==-50) { 
      main_count++; 
     } 
     for(j=0; j<COLS-1; j++) { 
      if((map[i][j]-map[i][j+1])==4) { 
       if(j==COLS-2 && (map[i][j+1]-map[i-1][j]-map[i-1][j+1])==-50) { 
        main_count++; 
       } 
       if(j!=COLS-2 && (map[i][j+1]-map[i-1][j]-map[i-1][j+1])-map[i-1][j+1]==-96) { 
        main_count++; 
       } 
      } 
     } 
    } 

    printf("Number of islands: %d\n", main_count); 

    return 0; 
} 

Answer 5

Asymptotically अपने दृष्टिकोण सबसे अच्छा हे (एन) है - यहाँ एक त्वरित प्रयास (कोड के लिए इतना पढ़ने योग्य नहीं है, लेकिन तेज ASCII artihmetics के उपयोग क्षमा) है।

पहले::

हालांकि, मैं चीजों की एक जोड़ी देखा

down, right, up, left, down-right, up-left, up-right, down-left 

एक बेहतर आदेश होगा:

अंदर समारोह आप क्रम में एक कोशिकाओं पड़ोसियों की जाँच markVisited :

left, right, up-left, up, up-right, down-left, down, down-right 

यह कैश में अच्छा खेलेंगे क्योंकि यह वर्तमान स्थिति के बगल में सीधे मूल्यों को पढ़कर शुरू होता है, और क्रमशः किसी दिए गए पंक्ति में।

(ध्यान दें कि विकर्णों से शुरू होने से बड़ी संख्या में स्थानों पर जाना होगा, लेकिन यह जांचने के बाद कि सेल का दौरा किया गया था या नहीं, केवल आखिरी जांच है कि यह किसी भी समय सहेज नहीं पाएगी)।

दूसरी बात:

किसी उपग्रह है कि केवल भूमि शामिल की सबसे खराब स्थिति में, अपने एल्गोरिथ्म प्रत्येक कोशिका कई बार (प्रत्येक पड़ोसी सेल है के लिए एक बार की तरह कुछ) का दौरा करेंगे।

इसका मतलब है कि आप लगभग आवश्यकतानुसार लगभग आठ गुना अधिक सरणी एक्सेस कर रहे हैं।

मुझे विश्वास है कि आप डेटा पर अधिक या कम रैखिक पास के साथ इस समस्या को हल कर सकते हैं।

मैं वर्तमान में एक दृष्टिकोण के बारे में सोच रहा हूं, अगर यह काम करता है तो मैं कोड को एक संपादन के रूप में जोड़ूंगा।