मैं किसी भी दिशा में दो आयामी सरणी कैसे खोजूं

Question

मैं सी # में एक शब्द खोज पहेली लिख रहा हूं और मैं शब्दों के लिए अक्षरों के दो आयामी सरणी को एक सुंदर तरीके से खोजना चाहता हूं।

दाएं, ऊपर से नीचे इत्यादि तक की मूल खोजों को लिखना मुश्किल नहीं है, हालांकि सरणी के पार तिरछे रूप से खोज करते समय चीजें थोड़ा वर्बोज़ शुरू हो रही हैं। मुझे यह काम मिल गया है लेकिन मुझे यकीन है कि वहाँ एक बेहतर समाधान है।

यहां एक पहेली का एक उदाहरण है जिसे मैं हल करने की कोशिश कर रहा हूं, किसी भी विचार की सराहना की जाएगी।

BXXD
AXEX
TRXX
FXXX

बैट फ्रेड

संपादित करें: परिणाम: मुझे कम्पास अंक खोज

संपादित करने के विचार देने के लिए स्टीव के लिए कुडोस खोज के लिए ar1, y1 और x2, y2 ar के शब्दों के समन्वय को वापस करने की आवश्यकता है रे।

संपादित करें: सरणी को खोजने के लिए एक अच्छा एल्गोरिदम प्रदान करने के लिए एंटी के लिए धन्यवाद।

यह अंतिम परिणाम मैं आया था। मैंने इसे एंटी के जवाब में एल्गोरिदम पर आधारित किया है, जिसने इसे शुरुआत के लिए सरणी ऑफसेट्स और किसी भी शब्द के अंत में वापस करने के लिए संशोधित किया है। यह एल्गोरिदम एक वर्ड सर्च गेम का इस्तेमाल किया जा रहा है जिसे मैं अपने बच्चों के लिए डब्ल्यूपीएफ में लिख रहा हूं। मुझे मदद करने के लिए हर किसी के लिए धन्यवाद। जब मैं सम्मानजनक हो तो मैं ऐप पर एक लिंक पोस्ट करूंगा।

public class Range 
{ 
    public Range(Coordinate start, Coordinate end) 
    { 
     Start = start; 
     End = end; 
    } 

    public Coordinate Start { get; set; } 
    public Coordinate End { get; set; } 
} 

public class Coordinate 
{ 
    public Coordinate(int x, int y) 
    { 
     X = x; 
     Y = y; 
    } 

    public int X { get; set; } 
    public int Y { get; set; } 
} 

public class WordSearcher 
{ 
    public WordSearcher(char[,] puzzle) 
    { 
     Puzzle = puzzle; 
    } 

    public char[,] Puzzle { get; set; } 

    // represents the array offsets for each 
    // character surrounding the current one 
    private Coordinate[] directions = 
    { 
     new Coordinate(-1, 0), // West 
     new Coordinate(-1,-1), // North West 
     new Coordinate(0, -1), // North 
     new Coordinate(1, -1), // North East 
     new Coordinate(1, 0), // East 
     new Coordinate(1, 1), // South East 
     new Coordinate(0, 1), // South 
     new Coordinate(-1, 1) // South West 
    }; 

    public Range Search(string word) 
    { 
     // scan the puzzle line by line 
     for (int y = 0; y < Puzzle.GetLength(0); y++) 
     { 
      for (int x = 0; x < Puzzle.GetLength(1); x++) 
      { 
       if (Puzzle[y, x] == word[0]) 
       { 
        // and when we find a character that matches 
        // the start of the word, scan in each direction 
        // around it looking for the rest of the word 
        var start = new Coordinate(x, y); 
        var end = SearchEachDirection(word, x, y); 
        if (end != null) 
        { 
         return new Range(start, end); 
        } 
       } 
      } 
     } 
     return null; 
    } 

    private Coordinate SearchEachDirection(string word, int x, int y) 
    { 
     char[] chars = word.ToCharArray(); 
     for (int direction = 0; direction < 8; direction++) 
     { 
      var reference = SearchDirection(chars, x, y, direction); 
      if (reference != null) 
      { 
       return reference; 
      } 
     } 
     return null; 
    } 

    private Coordinate SearchDirection(char[] chars, int x, int y, int direction) 
    { 
     // have we ve moved passed the boundary of the puzzle 
     if (x < 0 || y < 0 || x >= Puzzle.GetLength(1) || y >= Puzzle.GetLength(0)) 
      return null; 

     if (Puzzle[y, x] != chars[0]) 
      return null; 

     // when we reach the last character in the word 
     // the values of x,y represent location in the 
     // puzzle where the word stops 
     if (chars.Length == 1) 
      return new Coordinate(x, y); 

     // test the next character in the current direction 
     char[] copy = new char[chars.Length - 1]; 
     Array.Copy(chars, 1, copy, 0, chars.Length - 1); 
     return SearchDirection(copy, x + directions[direction].X, y + directions[direction].Y, direction); 
    } 
} 

Answer 1

इस समाधान सी में लिखा है ++ लेकिन सिद्धांत वही

अपने पहेली

char puzzle[N][N] 

का प्रतिनिधित्व करती है, तो है सरणियों की घोषणा

int xd[8] = { -1, -1, 0, +1, +1, +1, 0, -1 }; 
int yd[8] = { 0, -1, -1, -1, 0, +1, +1, +1 }; 

और फिर जब तुम जाँच करना चाहते हैं यदि शब्द 'डब्ल्यू' स्थान डी (डी, डी) में दिशा डी (डी, 0 के बीच) में पाया जा सकता है, तो बस

करें

bool wordsearch(const char *w, int x, int y, int d) { 
    if (*w == 0) return true; // end of word 
    if (x<0||y<0||x>=N||y>=N) return false; // out of bounds 
    if (puzzle[y][x] != w[0]) return false; // wrong character 
    // otherwise scan forwards 
    return wordsearch(w + 1, x + xd[d], y + yd[d], d); 
} 

और फिर ड्राइवरों

bool wordsearch(const char *w, int x, int y) { 
    int d; 
    for (d=0;d<8;d++) 
    if (wordsearch(w, x, y, d)) return true; 
    return false; 
} 

bool wordsearch(const char *w) { 
    int x, y; 
    for (x=0;x<N;x++) for(y=0;y<N;y++) if (wordsearch(w, x, y)) return true; 
    return false; 
} 

Answer 2

प्रत्येक शब्द के पहले अक्षर को किसी सूची या कुछ ऐसी डेटा संरचना में ढूंढने के लिए रखें। क्रम में हर पत्र खोजें। यदि यह एक शब्द का पहला अक्षर है जिसे आप खोज रहे हैं, तो उसके आस-पास के प्रत्येक अक्षर को दूसरे अक्षर के लिए खोजें। यदि आपको किसी शब्द में दूसरा अक्षर मिलता है तो उस शब्द ऑब्जेक्ट में दिशा को नोट करें जिसमें दिशा enum है, यानी {N = 0, NE, E, SE, S, SW, W, NW}। फिर बस उस दिशा का पालन करें जब तक कि आपने यह निर्धारित नहीं किया है कि शब्द नहीं मिला है या पाया गया है। खोज कुंजी के लिए वे कुंजी यह जानना चाहते हैं कि यह कितने शब्द देख रहा है। तो यदि आप दोनों कैटर और मवेशियों की तलाश में हैं, तो यदि आप सी-ए-टी पूर्वोत्तर में जाते हैं, तो यह भी हो सकता है। इसके अलावा, अगर आपको एफ मिलती है तो आपको हर दिशा की जांच करनी होगी क्योंकि आप पूर्व में जा रहे हैं और एफएटी पश्चिम जा रहा है। तो यह सुनिश्चित करें कि आप सीमा से बाहर नहीं जाते क्योंकि NE है बनाने के रूप में सरल है एक्स + 1 Y-1, आदि ...

Answer 3

यह विशिष्ट समस्या जहां trie डेटा संरचना का उपयोग करना चाहिए है: http://en.wikipedia.org/wiki/Trie

एक बार जब आप अपने दो आयाम सरणी की प्रत्येक स्थिति के माध्यम से सभी लक्षित शब्दों के साथ एक शब्दकोश प्राप्त कर लेते हैं और एक पुनरावर्ती कार्य को कॉल करते हैं जो सभी 8 तरीकों का विस्तार करता है। लाइनों के साथ कुछ।

void Explore(TwoDimArray puzzle, Point2D currentCell, string currentMatch, List<string> foundSolutions); 

आप रोक recursiveness यदि:
- आप कोई मेल मिलता है।
- वर्तमान मैच + वर्तमानसेल का चरित्र अब एक संभावित मैच नहीं बना रहा है।
- वर्तमान क्षेत्र स्थिति अब पहेली क्षेत्र के अंदर नहीं है।

Answer 4

पहेली के लिए 2 आयामी सरणी का उपयोग न करें। एक एनएक्सएम शब्द खोज के लिए, (एन + 2) * (एम + 2) की एक सरणी का उपयोग करें। अपनी पहेली के चारों तरफ 1 चरित्र की पैडिंग रखें। तो उदाहरण बन जाता है:

 
...... 
.BXXD. 
.AXEX. 
.TRXX. 
.FXXX. 
...... 

जहां अवधि पैडिंग होती है और यह सब वास्तव में एक 1 डी सरणी है।

पंक्ति ग्रेन (एस) की नई ग्रिड की चौड़ाई को कॉल करते हुए, अब आप 8 दिशा "वैक्टर" डी = [-एस -1, -एस, -एस + 1, -1, 1 की एक सरणी बना सकते हैं , एस -1, एस, एस + 1]। इसका उपयोग करके, आप पहेली [स्थिति + डी [दिशा]] का उपयोग कर किसी भी दिशा में ग्रिड पहेली [स्थिति] में अपने पड़ोसी के किसी भी स्थिति से देख सकते हैं।

पाठ्यक्रम की आपकी स्थिति अब निर्देशांक की एक जोड़ी के बजाय एक चरणीय है। सीमा के चारों ओर पैडिंग आपको बताती है कि क्या आप बोर्ड के किनारे तक पहुंच गए हैं और एक चरित्र होना चाहिए जिसका उपयोग कभी भी पहेली के इंटीरियर में नहीं किया जाता है।

Answer 5

public class Range 
{ 
    public Range(Coordinate start, Coordinate end) 
    { 
     Start = start; 
     End = end; 
    } 

    public Coordinate Start { get; set; } 
    public Coordinate End { get; set; } 
} 

public class Coordinate 
{ 
    public Coordinate(int x, int y) 
    { 
     X = x; 
     Y = y; 
    } 

    public int X { get; set; } 
    public int Y { get; set; } 
} 

public class WordSearcher 
{ 
    public WordSearcher(char[,] puzzle) 
    { 
     Puzzle = puzzle; 
    } 

    public char[,] Puzzle { get; set; } 

    // represents the array offsets for each 
    // character surrounding the current one 
    private Coordinate[] directions = 
    { 
     new Coordinate(-1, 0), // West 
     new Coordinate(-1,-1), // North West 
     new Coordinate(0, -1), // North 
     new Coordinate(1, -1), // North East 
     new Coordinate(1, 0), // East 
     new Coordinate(1, 1), // South East 
     new Coordinate(0, 1), // South 
     new Coordinate(-1, 1) // South West 
    }; 

    public Range Search(string word) 
    { 
     // scan the puzzle line by line 
     for (int y = 0; y < Puzzle.GetLength(0); y++) 
     { 
      for (int x = 0; x < Puzzle.GetLength(1); x++) 
      { 
       if (Puzzle[y, x] == word[0]) 
       { 
        // and when we find a character that matches 
        // the start of the word, scan in each direction 
        // around it looking for the rest of the word 
        var start = new Coordinate(x, y); 
        var end = SearchEachDirection(word, x, y); 
        if (end != null) 
        { 
         return new Range(start, end); 
        } 
       } 
      } 
     } 
     return null; 
    } 

    private Coordinate SearchEachDirection(string word, int x, int y) 
    { 
     char[] chars = word.ToCharArray(); 
     for (int direction = 0; direction < 8; direction++) 
     { 
      var reference = SearchDirection(chars, x, y, direction); 
      if (reference != null) 
      { 
       return reference; 
      } 
     } 
     return null; 
    } 

    private Coordinate SearchDirection(char[] chars, int x, int y, int direction) 
    { 
     // have we ve moved passed the boundary of the puzzle 
     if (x < 0 || y < 0 || x >= Puzzle.GetLength(1) || y >= Puzzle.GetLength(0)) 
      return null; 

     if (Puzzle[y, x] != chars[0]) 
      return null; 

     // when we reach the last character in the word 
     // the values of x,y represent location in the 
     // puzzle where the word stops 
     if (chars.Length == 1) 
      return new Coordinate(x, y); 

     // test the next character in the current direction 
     char[] copy = new char[chars.Length - 1]; 
     Array.Copy(chars, 1, copy, 0, chars.Length - 1); 
     return SearchDirection(copy, x + directions[direction].X, y + directions[direction].Y, direction); 
    } 
}