[종만북] BOGGLE

5*5 배열크기라 무지성 DFS인줄 알았는데 DP였다.
https://algospot.com/judge/problem/read/BOGGLE

일단 TLE난 코드를 올리고, 내일모래 DP로 최적화하기로 한다.

#include <bits/stdc++.h>
#define endl '\n'
#define FOR(i,n) for(int i=0;i<(n);++i)
using namespace std;

int t,query_num;
string box[5];
bool visited[5][5];
vector<string> query;
int dr[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dc[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

int is_in(int r, int c){
    if(r>=5||c>=5||r<0||c<0) return false;
    return true;
}

bool search_start(string& target, int r, int c, int idx){
    if(idx==target.length()){
        return true;
    }
    FOR(i,8){
        int rr = r+dr[i]; int cc=c+dc[i]; 
        if(!is_in(rr,cc) || box[rr][cc]!=target[idx]) continue;
        visited[rr][cc]=true;
        bool result = search_start(target,rr,cc,idx+1);
        visited[rr][cc]=false;
        if(result) return true;
    }
    return false;
}

void solve(){
    for(auto target:query){
        FOR(r,5){
            FOR(c,5){
                if(target[0]!=box[r][c]) continue;
                visited[r][c]=true;
                bool result = search_start(target,r,c,1);
                visited[r][c]=false;
                if(result) {
                    cout<<target<<" YES"<<endl;
                    goto finished;
                }
            }
        }
        cout<<target<<" NO"<<endl;
        finished: ;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>t;
    while(t--){
        FOR(i,5){
            cin>>box[i];
        }
        cin>>query_num;
        FOR(i,query_num){
            string tmp;
            cin>>tmp;
            query.push_back(tmp);
        }
        solve();
        query.clear();
        FOR(i,5) box[i].clear();
    }
    return 0;
}