보글 게임

//알고리즘 문제해결전략 챕터: 완전탐색 예제 : 보글게임

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

char board[5][5]={{'U', 'R', 'L', 'P', 'M'},
    {'X', 'P', 'R', 'E', 'T'},
    {'G', 'I', 'A', 'E', 'T'},
    {'X', 'T', 'N', 'Z', 'Y'},
    {'X', 'O', 'Q', 'R', 'S'}};

int dx[8]={-1, -1, 0, 1, 1, 1, 0, -1}, dy[8]={0, 1, 1, 1, 0, -1, -1, -1};

bool inRange(int x, int y){
    if(x>=0 && x<5 && y>=0 && y<5) return true;
    else return false;
}

bool hasWord(int x, int y , string s){
    //x, y가 범위 내에 있는지 확인
    if(!inRange(x, y)) return false;
    //첫 글자가 다르면 false를 리턴
    if(board[x][y]!=s[0]) return false;
    
    //앞서 첫 글자가 같은것을 확인하고 s의 크기가 1이면 true를 리턴
    if(s.size()==1) return true;
    
    for(int i = 0 ; i<8 ; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        //x, y에서 갈 수 있는 모든 칸을 검사(첫 글자는 앞서 검사했기 때문에 substr(1)로 첫 글자를 뺸 나머지 글자를 확인
        if(hasWord(nx, ny, s.substr(1))) return true;
    }
    return false;
}
int main(){
    if(hasWord(1, 1, "PRETTY")){
        printf("true");
    }else{
        printf("false");
    }
    return 0;
}