字搜索求解器

Question

下面的代码展示了我在创建字词搜索解谜器方面的经验，在这个解谜器中，单词被嵌入到一个被解析并适合于.txt的vector<vector<char>>文件中。然后，搜索输入的单词。

就有效的OOP而言，什么是分离程序的最佳方法？我应该创建两个单独的.cpp文件吗？-一个用来存储搜索函数，另一个用来存储迭代函数？此外，呈现用户界面的最佳方式是什么-- main()函数？是否也应该将其分离到另一个文件中？

另外，它在语法上可以使用什么呢？我认为迭代函数中位置的重新定义可能有点多余，可以减少。

/*

 Wordsearch Solver

 Program aims to find any inputted word within a .txt file containing square
 or rectangular puzzles, with characters not separated by spaces. If the word
 is found, prints the position of the first character of the word. Otherwise,
 prints -1 and -1. The eight common directions are tested - left, right, up,
 down, diagonally left-up, diagonally left-down, diagonally right-down, and
 diagonally right-up.

 For the diagonal search, assume a slope of 1. That is,
 1 unit left or right = 1 unit diagonally. To work with rectangular (not square) arrays,
 the minimum of the two diagonal directions is taken to be the number of remaining
 characters.

 Sample 40x40 found at end

 AA

 */

#include <iostream>
using std::cout; using std::endl;

#include <string>
using std::string;

#include <fstream>
using std::ifstream;

#include <sstream>
using std::istringstream;

#include <vector>
using std::vector;

#include <utility>
using std::pair; using std::make_pair;

#include <algorithm>
using std::min;

string spaced(string str) {
    /*
     Inputs a space between a non-space separated string.
     str: input string
     Return: a string with spaces in between the characters.

     Comment out if using .txt file characters already space separated.

     Found on cplusplus.com
     */
    if ( str == "" )
        return str;
    string result( 2 * str.size() - 1, ' ' );

    for ( int i = 0, j = 0; i < str.size(); i++, j+=2 )
        result[j] = str[i];

    return result;
}

vector<vector<char>> open_parse_file(string filename) {
    /*
     Parses a .txt file and creates the associated wordsearch puzzle of type vector<vector<char>>.
     filename: file to parse
     Return: a vector<vector<char>> wordsearch puzzle.
     */
    ifstream input_file;
    string line;

    vector<vector<char>> wordsearch;

    input_file.open(filename);

    while (getline(input_file, line)) {
        vector<char> temp_vec;
        string space_sep_line = spaced(line);
        istringstream iss(space_sep_line);
        char letter;

        while (iss) {
            iss >> letter;
            temp_vec.push_back(letter);
        }

        temp_vec.pop_back();  // iss puts extra char at end; remove it
        wordsearch.push_back(temp_vec);
    }
    return wordsearch;
}

pair<int, int> horizontal_forward_search(vector<vector<char>>  const&wordsearch, int row_num, int col_num, string word) {
    /*
     Searches horizontally and forward for a word matching the inputted word.
     wordsearch: the wordsearch puzzle
     row_num: the current row position in the array
     col_num: the current column position in the array
     word: the input word
     Return: the location
     */
    long remaining_chars = wordsearch[row_num].size() - col_num;

    if (word.size() > remaining_chars + 1)   // word size exceeds remaining characters plus 1 from current postion
        return make_pair(-1, -1);


    else {
        string temp_str = "";
        int cur_pos = col_num;
        int i = 0;
        while (i < word.size()) {
            char cur_letter = wordsearch[row_num - 1][cur_pos - 1];
            temp_str.push_back(cur_letter);
            ++cur_pos;  // next pos in array
            ++i;
        }
        if (temp_str == word)
            return make_pair(row_num, col_num);
    }
    return make_pair(-1,-1);

}

pair<int, int> horizontal_backward_search(vector<vector<char>> const& wordsearch, int row_num, int col_num, string word) {
    /*
     Searches horizontally and backwards for a word matching the inputted word.
     wordsearch: the wordsearch puzzle
     row_num: the current row position in the array
     col_num: the current column position in the array
     word: the input word
     Return: the location
     */
    long remaining_chars = col_num - 1;

    if (word.size() > remaining_chars + 1)
        return make_pair(-1, -1);

    else {
        string temp_str = "";
        int cur_pos = col_num;
        int i = 0;
        while (i < word.size()) {
            char cur_letter = wordsearch[row_num - 1][cur_pos - 1];
            temp_str.push_back(cur_letter);
            --cur_pos;
            ++i;
        }
        if (temp_str == word)
            return make_pair(row_num, col_num);
    }
    return make_pair(-1, -1);
}

pair<int, int> vertical_down_search(vector<vector<char>> const&wordsearch, int row_num, int col_num, string word) {
    /*
     Searches vertically and down for words matching the inputted word.
     wordsearch: the wordsearch puzzle
     row_num: the current row position in the array
     col_num: the current column position in the array
     word: the input word
     Return: the location
     */
    long remaining_chars = wordsearch.size() - row_num;

    if (word.size() > remaining_chars + 1)
        return make_pair(-1, -1);

    else {
        string temp_str = "";
        int cur_pos = row_num;
        int i = 0;
        while (i < word.size()) {
            char cur_letter = wordsearch[cur_pos - 1][col_num - 1];
            temp_str.push_back(cur_letter);
            ++cur_pos;
            ++i;
        }
        if (temp_str == word)
            return make_pair(row_num, col_num);
    }
    return make_pair(-1, -1);
}

pair<int, int> vertical_up_search(vector<vector<char>> const&wordsearch, int row_num, int col_num, string word) {
    /*
     Searches verticlally and up for words matching the inputted word.
     wordsearch: the wordsearch puzzle
     row_num: the current row position in the array
     col_num: the current column position in the array
     word: the input word
     Return: the location
     */
    long remaining_chars = row_num - 1;

    if (word.size() > remaining_chars + 1)
        return make_pair(-1, -1);

    else {
        string temp_str = "";
        int cur_pos = row_num;
        int i = 0;
        while (i < word.size()) {
            char cur_letter = wordsearch[cur_pos - 1][col_num - 1];
            temp_str.push_back(cur_letter);
            --cur_pos;
            ++i;
        }
        if (temp_str == word)
            return make_pair(row_num, col_num);
    }
    return make_pair(-1, -1);
}

pair<int, int> diagonal_left_up_search(vector<vector<char>> const&wordsearch, int row_num, int col_num, string word) {
    /*
     Searches diagonally left and up for words matching the inputted word.
     wordsearch: the wordsearch puzzle
     row_num: the current row position in the array
     col_num: the current column position in the array
     word: the input word
     Return: the location

     Assume slope of 1; 1 unit up or down = 1 unit diagonally.
     */
    long remaining_left = col_num - 1;
    long remaining_up = row_num - 1;
    long remaining_chars = min(remaining_left, remaining_up);

    if (word.size() > remaining_chars + 1)
        return make_pair(-1, -1);

    else {
        string temp_str = "";
        int cur_pos_v = row_num;
        int cur_pos_h = col_num;
        int i = 0;
        while (i < word.size()) {
            char cur_letter = wordsearch[cur_pos_v - 1][cur_pos_h - 1];
            temp_str.push_back(cur_letter);
            --cur_pos_v; //vertically
            --cur_pos_h; //horizontally
            ++i;
        }
        if (temp_str == word)
            return make_pair(row_num, col_num);
    }
    return make_pair(-1, -1);
}

pair<int, int> diagonal_left_down_search (vector<vector<char>> const&wordsearch, int row_num, int col_num, string word) {
    /*
     Searches diagonally left and down for words matching the inputted word.
     wordsearch: the wordsearch puzzle
     row_num: the current row position in the array
     col_num: the current column position in the array
     word: the input word
     Return: the location

     Assume slope of 1; 1 unit up or down = 1 unit diagonally.
     */
    long remaining_left = col_num - 1;
    long remaining_down = wordsearch.size() - row_num;
    long remaining_chars = min(remaining_left, remaining_down);

    if (word.size() > remaining_chars + 1)
        return make_pair(-1, -1);

    else {
        string temp_str = "";
        int cur_pos_v = row_num;
        int cur_pos_h = col_num;
        int i = 0;
        while (i < word.size()) {
            char cur_letter = wordsearch[cur_pos_v - 1][cur_pos_h - 1];
            temp_str.push_back(cur_letter);
            ++cur_pos_v;
            --cur_pos_h;
            ++i;
        }
        if (temp_str == word)
            return make_pair(row_num, col_num);
    }
    return make_pair(-1, -1);
}

pair<int, int> diagonal_right_up_search (vector<vector<char>> const&wordsearch, int row_num, int col_num, string word) {
    /*
     Searches diagonally right and up for words matching the inputted word.
     wordsearch: the wordsearch puzzle
     row_num: the current row position in the array
     col_num: the current column position in the array
     word: the input word
     Return: the location

     Assume slope of 1; 1 unit up or down = 1 unit diagonally.
     */
    long remaining_right = wordsearch[row_num].size() - col_num;
    long remaining_up = row_num - 1;
    long remaining_chars = min(remaining_right, remaining_up);

    if (word.size() > remaining_chars + 1)
        return make_pair(-1, -1);

    else {
        string temp_str = "";
        int cur_pos_v = row_num;
        int cur_pos_h = col_num;
        int i = 0;
        while (i < word.size()) {
            char cur_letter = wordsearch[cur_pos_v - 1][cur_pos_h - 1];
            temp_str.push_back(cur_letter);
            --cur_pos_v;
            ++cur_pos_h;
            ++i;
        }
        if (temp_str == word)
            return make_pair(row_num, col_num);
    }
    return make_pair(-1, -1);
}

pair<int, int> diagonal_right_down_search (vector<vector<char>> const&wordsearch, int row_num, int col_num, string word) {
    /*
     Searches diagonally right and down for words matching the inputted word.
     wordsearch: the wordsearch puzzle
     row_num: the current row position in the array
     col_num: the current column position in the array
     word: the input word
     Return: the location

     Assume slope of 1; 1 unit up or down = 1 unit diagonally.
     */
    long remaining_right = wordsearch[row_num].size() - col_num;
    long remaining_down = wordsearch.size() - row_num;
    long remaining_chars = min(remaining_right, remaining_down);

    if (word.size() > remaining_chars + 1)
        return make_pair(-1, -1);

    else {
        string temp_str = "";
        int cur_pos_v = row_num;
        int cur_pos_h = col_num;
        int i = 0;
        while (i < word.size()) {
            char cur_letter = wordsearch[cur_pos_v - 1][cur_pos_h - 1];
            temp_str.push_back(cur_letter);
            ++cur_pos_v;
            ++cur_pos_h;
            ++i;
        }
        if (temp_str == word)
            return make_pair(row_num, col_num);
    }
    return make_pair(-1, -1);
}

pair<int, int> iterate(vector<vector<char>> const&wordsearch, string word) {
    /*
     Iterates through the wordsearch to find the inputted word
     wordsearch: the wordsearch puzzle
     word: the inputted word
     Return: the location
     */

    int row_num = 0;
    for (vector<char> row: wordsearch) {
        ++row_num;
        int col_num = 0;
        for (char letter: row) {
            ++col_num;
            if (letter == word[0]) {  // first letter of word found, confirm/deny word
                // Perform the 8 possible searches.
                pair<int, int> location = horizontal_forward_search(wordsearch, row_num, col_num, word);
                if (location.first != -1)
                    return location;
                location = horizontal_backward_search(wordsearch, row_num, col_num, word);
                if (location.first != -1)
                    return location;
                location = vertical_down_search(wordsearch, row_num, col_num, word);
                if (location.first != -1)
                    return location;
                location = vertical_up_search(wordsearch, row_num, col_num, word);
                if (location.first != -1)
                    return location;
                location = diagonal_left_up_search(wordsearch, row_num, col_num, word);
                if (location.first != -1)
                    return location;
                location = diagonal_left_down_search(wordsearch, row_num, col_num, word);
                if (location.first != -1)
                    return location;
                location = diagonal_right_up_search(wordsearch, row_num, col_num, word);
                if (location.first != -1)
                    return location;
                location = diagonal_right_down_search(wordsearch, row_num, col_num, word);
                if (location.first != -1)
                    return location;
            }
        }
    }
    return make_pair(-1, -1);
}

int main() {
    // Input information here
    vector<vector<char>> wordsearch = open_parse_file("input text file here");
    pair<int, int> location = iterate(wordsearch, "input word here");
    cout << location.first << " and " << location.second << endl;

} 


/*
 Sample 40x40 wordsearch

 khtjbobelbllelawrlafpsikeujttiefgpedzdud
 urrrzlmqesrtijulktjralhhoxbcupgchakqylin
 mjagawzurirorotsqbogbsacqleejcyshtddkpbg
 qtnknpniunpexeoxxdrzoncntunpqsdsjhmyhfcc
 snitnirptblbmmheuoiyhyvbnintcmxsdzpaijau
 kperformancecoatxzpggmudhilkqhnqovcltrkf
 msupplierkvrljtloxnonsgrtingsfbdyjzcwmly
 dnbcvienehbdriisjmlviineotggpiryhiqmsdlp
 yejzssctpnsdozoduofnpglwzccjiouxrqtpdxhj
 gzgxnsckmaintenanceppgwortegisqfjttetuwb
 npbzdixiesrgomahxssniserolpjxsezzaxigldl
 iqnmwfwotmktnhctsruahcckjtynndmdovkxbcmc
 rkuqdzerjsassemblyobsaqpuqxuigrvmzannsmh
 uawfrcigetartshitmcuqcazsnfespmbkfhyeqxt
 tapvwbgjgdmlgwtiydvyikzvuywugdytzxbntudn
 ccpeufynjgrjptlaqetyhizeacffaqomnxfemcvh
 ambtzwbtbmyalarjbawkvabosyzrpxdnllaqyeel
 fdijsposyiieueupauwkvffbjtmscktfqbvnuryr
 uogubvhiasrqgqxzedpgtjfbsveeibhjkjeyqdsa
 nlsfwxikkffwzwdpqubyfcexdmxebspdbienytxr
 avmuvxraxqwogzzewzpqurndrbmbtoewyknigrgy
 mlfmsvczbnbfatlcqoilvqjgenhxeyxotnndymgd
 tdoylwblacsswaazrsqptrhskjskpacmbyoghxdq
 doqwnpemhtqqmfmstgyveegbzhiszqjrzgfjhgnr
 yzkctjdotnjwzslxjlxvywjpjkovnrsqoqcazwxi
 hldcmmhadrndojumhjvtrsjkzzxwpokahglbcfll
 fghegxihojeqcdeaejzfzeksqgkhetngnmlmkhqb
 erubfrtmbalpnnljfseheugkxqaolhjwzqunleuh
 lfmnqjfbzyypmehzizhyurdsxmioejyeihfotmkc
 ufvtnqgaquifugqpwnpsvbwkplwehrqqpvahrzuh
 ukiwxtnqtztnuaeqdanzpspphaqsiaomsallnalt
 mfxmnbpxwhjlcjxstcxpymgazvlbubdymgdjytga
 nodglgayixlwfndioqswwarbaybtkhqmagoksgos
 auuoyzvwbaxlaalsedsciwdfaqgzypizluekliet
 rdldaqlveysukdutwutkyyjswzdvnfextdojspui
 ipmgltqauypamxssoppeygwgpftounkaxerwfkrt
 cfhiifkyvtvxnegqlmpbbckbexscntziitkrglmh
 zpqlaolbocqijyvbmxegdjnextlmciytfgedfdjg
 ritzgiuksqcaiqvwajjajydolwcxzxlwmdkvchua
 dinflhovqslcmnfigvjsvitfotytytqtccmtrvdl

 */

Answer 1

实际上，我最近做了这样的事情，是为了一个编码挑战。

我选择创建两个单独的类。一个是读取器类，它从文件中读取数据并将数据提供给Grid类。然后，Grid类使用开始时所有可能的单词组合来初始化自己。这样就可以很容易地找到单词，因为它只需要在一组中调用"find“。

如果您希望为此添加一个额外的接口，那么我将将其添加为一个单独的类。这个类将处理将用户输入转换为对reader/writer类的调用，后者反过来对Grid类进行调用。如果您的接口足够简单(也就是说，您只想输入哪个文本文件应该由您的读取器/写入器类读取)，这可以只在main()中完成，但是如果您想在将来使其可移植，则单独的类会更好。

特别是在代码中，我在实现中看到的最大问题是，您有8个独立的函数，它们或多或少地完成了相同的任务。您应该尝试将其抽象出来，并在单个方法中全部完成。我在网格的“GenerateWords”法中有一个例子。

    while (iss) {
        iss >> letter;
        temp_vec.push_back(letter);
    }

如果你只是简单地检查一下，

    while (iss >> letter) {
        temp_vec.push_back(letter);
    }

你会发现没有一个“额外”的信被添加到末尾。