6장 보글게임(BOGGLE 동적계획법 적용하기전)

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cassert>
using namespace std;
 
int ny[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int nx[8] = {  0,  1, 1, 1, 0,-1,-1, -1 };
string board[5];
bool Findword(const string& s, int y, int x) {
    //기저사례 범위 밖을 벗어나는 경우
    if (y < 0 || y >= 5 || x < 0 || x >= 5) return false;
    //기저사례 첫글자가 일치하지 않으면 실패
    if (board[y][x]!=s[0]) return false;
    //기저사례 단어길이가 1이면 성공
    if (s.size() == 1) return true;
 
    for (int direction = 0; direction < 8; direction++) {
        int Nexty = y + ny[direction];
        int Nextx = x + nx[direction];
        if (Findword(s.substr(1), Nexty, Nextx))
            return true;
    }
    return false;
}
 
int main()
{
    int cases;
    cin >> cases;
    assert(cases <= 50);
    while (cases) {
        for (int i = 0; i < 5; i++) {
            cin >> board[i];
        }
        int N;
        cin >> N;
        for (int i = 0; i < N; i++) {
            string s;
            cin >> s;
            bool Check = false;
            for (int a = 0; a < 5; a++) {
                for (int b = 0; b < 5; b++) {
                    if (board[a][b] == s[0]) {
                        Check = Findword(s, a, b);
                        if (Check)
                            break;
                    }
                }
                if (Check)
                    break;
            }
            if (Check)
                cout << s << " " << "YES\n";
            else
                cout << s << " " << "NO\n";
                
        }
    }
    return 0;
}
 

문제 출처:https://algospot.com/judge/problem/read/BOGGLE

이 문제는 8장의 동적 계획법을 적용하기 전에는 해결 할 수 없습니다만.. 8장은 아직 진도를 나가고 있는 중이기 때문에

6장의 동적계획법 적용전인 완전 탐색으로 구현을 해보았습니다.

추후에 더 공부하고 동적 계획법 적용 후의 코드를 올리도록 하겠습니다.