BOGGLE

https://algospot.com/judge/problem/read/BOGGLE

algospot.com :: BOGGLE

 

cache[x][y][idx]를 이용해서 현재 위치 (x,y)에서 idx까지 탐색했을 때 중복 탐색 여부를 확인해준다. 그러면 탐색 가지수를 줄일 수 있다.

 

#include <cstdio>
#include <cstring>

int t,n,len;
char map[7][7],s[15];
int cache[5][5][10];
int dx[8]={-1,-1,-1,0,0,1,1,1};
int dy[8]={-1,0,1,-1,1,-1,0,1};

bool go(int x,int y,int idx)
{
    if(x<0 || x>4 || y<0 || y>4 || cache[x][y][idx] || map[x][y]!=s[idx])
        return false;
    cache[x][y][idx]=1;
    if(idx==len-1)
        return true;
    for(int i=0;i<8;i++)
        if(go(x+dx[i],y+dy[i],idx+1))
            return true;
    return false;
}

bool find()
{
    for(int i=0;i<5;i++)
        for(int j=0;j<5;j++)
            if(go(i,j,0))
                return true;
    return false;
}

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        for(int i=0;i<5;i++)
            scanf("%s",map[i]);
        scanf("%d",&n);
        while(n--)
        {
            scanf("%s",s);
            len=strlen(s);
            memset(cache,0,sizeof(cache));
            printf("%s %s\n",s,find()?"YES":"NO");
        }
    }
    return 0;
}