कोई भी 2 डी सरणी में "आकार" खोजने के लिए एल्गोरिदम जानता है?

Question

चलिए इस मानचित्र को लेते हैं, जहां '#' एक लिया गया वर्ग दिखाता है और '।' एक नि: शुल्क वर्ग दिखाता है:

 
1 . # # # . . 
2 . # . . # . 
3 # . . . . # 
4 . # # # . . 
5 . . . . . . 
6 . . . . . . 
- 1 2 3 4 5 6 

अब, अगर मैं वर्ग 4,5 में एक '#' डाल क्षेत्र इस तरह "भरा" की जाएगी:

 
1 . # # # . . 
2 . # # # # . 
3 # # # # # # 
4 . # # # # . 
5 . . . . . . 
6 . . . . . . 
- 1 2 3 4 5 6 

तो, क्या सबसे अच्छा है "एक सीमित वर्ग" खोजने का तरीका, जहां मैं बाढ़ भरना शुरू कर सकता हूं या सीमित क्षेत्र को भरने वाले अन्य एल्गोरिदम भर सकता हूं?

Answer 1

यदि आप अपनी समस्या को किसी ग्राफ में परिवर्तित कर सकते हैं, तो आप जो खोज रहे हैं वह कनेक्ट किए गए घटकों की पहचान करना है। और यदि किसी कनेक्टेड घटक में धार किनारे नहीं हैं, तो आपको उस क्षेत्र को मिला है जिसे भरने की आवश्यकता है।

अगर मैं इस तरह ग्राफ को परिभाषित:

G = (V, E) 
V = {r1, r2, r3, r4, r5, r6, c1, c2, c3, c4, c5, c6} 
E = {(u, v) | u, v are elements of V && the cell(u, v) is not taken} 

अब DFS चलाने सभी कट पेड़ लगाने के लिए। एल्गोरिदम:

for each u in V: 
    color[u] = white 

for each u in V: 
    if color[u] == white: 
     contains_boundary_edge = False 
     DFS-visit(u, contains_boundary_edge) 

     if not contains_boundary_edge: 
      Flood-fill(u) 

DFS-visit(u, contains_boundary_edge): 
    color[u] = gray 
    for each v in adjacent(u): 
     if color[v] == white: 
      if edge(u, v) is a boundary edge: // Can be easily identified if one of u, v is start or end row/col. 
       contains_boundary_edge = True 

      DFS-visit(v, contains_boundary_edge) 

    color[u] = black 

Answer 2

मुझे लगता है कि इस सवाल का एक उत्तल पतवार समस्या को कम किया जा सकता है, तो हम एक # के रूप में बिंदु एक्स पर विचार, वाई तो उत्तल पतवार हमें एक्स सब # जो अनुपस्थित रहे हैं के y देते हैं, हो सकता है

http://en.wikipedia.org/wiki/Convex_hull

मैं इसे अवकाश में कोड करने की कोशिश करूंगा ..

Answer 3

आप प्रत्येक '।' को संसाधित करके इसका हमला कर सकते हैं। नोड।

परिभाषा: ए '।' नोड संलग्न है यदि नोड से नक्शे की सीमा तक कोई पथ मौजूद नहीं है।

यदि आप उपर्युक्त परिभाषा से सहमत हैं, तो एल्गोरिदम '।' का ग्राफ बनाए रखना होगा। नोड्स, जहां आसन्न नोड जुड़े हुए हैं।

हर बार एक नोड को '#' में बदल दिया जाता है, इसे इस ग्राफ से हटा दें, और प्रत्येक शेष '।' यह देखने के लिए नोड नक्शा सीमा पर नोड्स में से एक में से एक पथ मौजूद है या नहीं।

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

Answer 4

यदि आप इस मानचित्र को ग्राफ के रूप में मॉडल करते हैं, और प्रत्येक वर्ग अपने चार पड़ोसियों से जुड़ा हुआ है, तो आप जिस वर्ग को चाहते हैं उसे ढूंढने के लिए आप bridge finding algorithm का उपयोग कर सकते हैं।

नोट करें कि यह मॉडल आपको कभी-कभी काम करने के लिए कई उप-अनुच्छेद देता है, इसलिए यह # जोड़ने के बाद से सीमा के चारों ओर कई झूठी सकारात्मक उत्पन्न कर सकता है, निश्चित रूप से बाकी से कुछ नोड्स अलग कर देंगे। इसके आस-पास पहुंचने के लिए, आप ग्राफ़ के चारों ओर वर्गों के दो स्तर पैड कर सकते हैं, ताकि कोई भी # बाकी से सीमा नोड को अलग कर सके।

@ svick की टिप्पणी ने इस विधि को प्रेरित किया।

Answer 5

मैं उठाए गए वर्ग के प्रत्येक पड़ोसी से शुरू करूंगा, और ग्रिड की सीमा तक 'भागने' की कोशिश करूंगा। इस बीच, 'एक्स' के बाद पथ चिह्नित करें। यदि आप बच सकते हैं: प्रत्येक 'एक्स' पूर्ववत करें। यदि आप भाग नहीं सकते हैं, तो '#' से प्रत्येक 'एक्स' को प्रतिस्थापित करें। जैसा कि नीचे दिखाया गया है, मैंने जावा में एक उदाहरण बनाया है।

int W, H; 
char[][] input; 
final int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; 

public void handle(int x, int y) { 
    // try each neihgbor 
    for (int[] d : directions) { 
     if (canEscape(input, x, y)) { 
      // if we can escape, the path found shouldn't be filled 
      // so replace the Xes by '.'; 
      handleXes(input, false);     
     } else { 
      // if we cannot escape, this is a closed shape, so 
      // fill with '#' 
      handleXes(input, true); 
     } 
     // note that this can be written more concisely as 
     // handleXes(input, !canEscape(input, x, y)); 
    } 
}  

public boolean canEscape(char[][] grid, int x, int y) { 
    if (isEscape(grid, x, y)) 
     return true 

    if (isValid(grid, x, y)) { 
     // mark as visited 
     grid[x][y] = 'X'; 
     // try each neighbor 
     for (int[] d : directions) { 
      if (canEscape(grid, x+d[0], y+d[1])) 
       return true; 
     } 
    } 

    return false; 
} 

public boolean isValid(char[][] grid, int x, int y) { 
    return 0 <= x && x < W && 0 <= y && y < H && grid[x][y] == '.'; 
} 

public boolean isEscape(char[][] grid, int x, int y) { 
    return (0 == x || x == W-1 || 0 == y || y == H-1) && grid[x][y] == '.'; 
} 

public void handleXes(char[][] grid, boolean fill) { 
    for (int x = 0; x < W; x++) 
     for (int y = 0; y < H; y++) 
      if (grid[x][y] == 'X') 
       grid[x][y] = fill ? '#' : '.'; 
}