[Algospot] BOGGLE C++

今日の問題は完全に探索を利用して解決したボグゲームです!
問題は以下の通りです.

ゲーム

Boggle(Boggle)ゲームは、図(a)のような5 x 5サイズのアルファベットグリッドです.
ゲームはゲームボードの1文字から始まり、ペンを動かして出会った文字を順番に並べ、英語の単語を見つけるゲームです.ペンは上下左右に移動したり、対角線を隣のセルに移動したりして、文字をスキップすることはできません.過去の字はもう一度書き直すことができるが、同じ字を何度も筆を動かさずに書くことはできない.
例えば、図中の(b)、(c)、(d)は、各(a)メッシュにおいてPRETTY、GIRL、およびREPEATを検索した結果を示す.
碁盤と既知の単語のリストが与えられると、各単語が見つかるかどうかを出力するプログラムを作成します.

入力

入力された最初の行は、テストケースの数C(C<=50)を示します.各テストケースの最初の行には、5行ごとに5文字の碁盤格子があります.ゲームボードのすべてのセルはアルファベットで大文字です.
次の行は、我々が知っている単語数N(1<=N<=10)を与える.その後のN行には、どの行にも私たちが知っている単語があります.各単語は、1つまたは10文字の大文字またはそれ以下のアルファベットから構成されます.

しゅつりょく

各テストケースはN行を出力する.各行は入力で指定した順序で知っている単語を出力し,その単語が見つかった場合はYES,そうでなければNOを出力する.

入力例

1
URLPM
XPRET
GIAET
XTNZY
XOQRS
6
PRETTY
GIRL
REPEAT
KARA
PANDORA
GIAZAPX

サンプル出力

PRETTY YES
GIRL YES
REPEAT YES
KARA NO
PANDORA NO
GIAZAPX YES

この問題は[アルゴリズム]です
これは『問題解決策』の無知な解答部分に現れた最初の問題である.
「無知な解答」というテーマのように、可能な限りの数を探索する完全な探索方法で解決できる問題です!
初めて出会った完全探索問題なので、まず本の解答を見て、それから注釈をして、それからコードを書きました.

問題を解く

1つの簡単な方法は、完全なナビゲーションを使用して単語が見つかるまで、隣接する各セルを試します.
与えられた文字の最初の文字が黒板上のどこにも存在しない場合は、NOを出力すべきです!
¥なので、与えられた文字の最初の文字が碁盤にあるかどうかをチェックしてから問題を解きます.
指定された文字の最初の文字が碁盤に見つかった場合は、見つかった碁盤の位置に接する場所で見つければよい.ここで同じ仕事が繰り返されていることに気づきやすい!
指定された単語の最初のアルファベットが黒板に存在するかどうか
碁盤上に存在する場合は、次に、与えられた単語の最初の文字以外の単語がその近くにあるかどうかを確認する.こんな小さな同じ作業で分解できる問題は、「再帰」で完全に探求して解決することができます!
では、再帰関数から抜け出すのはいつですか.
1.指定された単語の最初の文字でない場合、常に失敗します.
2.1番に当てはまらなければ、欲しい単語が1文字なら、いつも成功!
以上の2つの条件の間の順序は絶対に変えられません!
これは、順序を変更して、自分でデバッグできるからです:)

コード#コード#

参考書の説明で書かれたコードは以下の通りです.

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// 맵 이동을 위한 direction vector
const vector<int> dX = {-1, -1, -1, 0 ,0, 1, 1, 1};
const vector<int> dY = {1, 0, -1, 1, -1, 1, 0, -1};

vector< string > mapp(5, "-----");


bool hasWord(int, int, const string &);

int main() {
    // 맵 사이즈 입력 받기
    int testcase;
    cin >> testcase;


    while (testcase--) {

        // 게임 맵 입력받기
        for(int i=0; i<5; i++){
            cin >> mapp[i];
        }


        int cnt;
        cin >> cnt;

        for (int i = 0; i < cnt; i++) {
            string word;
            cin >> word;
            cout << word << " ";
            bool exist = false;
            for (int r = 0; r < 5; r++) {
                for (int c = 0; c < 5; c++) {
                    if (mapp[r][c] == word[0]) {
                        if (hasWord(r, c, word)) {
                            exist = true;
                        }
                    }
                }
            }
            if (exist)
                cout << "YES" << endl;
            else
                cout << "NO" << endl;
        }

    }
    return 0;
}

bool hasWord(int y, int x, const string& word){

    // base case 1: 시작 위치가 게임 맵 범위 밖이면 실패
    if (y < 0 || y >= 5 || x < 0 || x >= 5)
        return false;

    // base case 2: 첫 글자가 일치하지 않으면 실패
    if (mapp[y][x] != word[0])
        return false;

    // base case 3: 단어 길이가 1이면 성공
    if (word.size() == 1)
        return true;

    // 인접한 8칸 검사하기
    for (int direction=0; direction<8; direction++){
        int nextY = y + dY[direction];
        int nextX = x + dX[direction];
        // 다음 칸이 범위 안에 있는지, 첫글자는 일치하는지 확인할 필요 없음 (기저사례에 존재)
        if (hasWord(nextY, nextX, word.substr(1))){
            return true;
        }
    }
    return false;
}

答えは正しいですが、採点するとタイムアウトが発生します.
もちろん、完全探索を利用して解決しているので、時間制限がなければ当然の結果です.
次に、DP(ダイナミックプログラミング)を使って問題を素早く解決してみましょう!
質問元:https://www.algospot.com/judge/problem/read/BOGGLE