백준 2210번: 숫자판 점프 (C++)

https://www.acmicpc.net/problem/2210

2210번: 숫자판 점프

---

Solved By: DFS

 

 

#include <iostream>
#include <set>
using namespace std;

string board[6][6];
bool visited[6][6];

struct Dir{
    int y, x;
};

Dir dir[4] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int res = 0;
set<string> st;

void dfs(int y, int x, string s){
    if(s.length() == 6){
        if(!st.count(s)){
            //cout << s << '\n';
            st.insert(s);
            res++;
        }
        return;
    }
    
    
    for(int i = 0; i < 4; i++){
        int dy = y + dir[i].y;
        int dx = x + dir[i].x;
        if(dy < 1 || dy > 5 || dx < 1 || dx > 5) continue;
        dfs(dy, dx, s + board[dy][dx]);
    }
}

int main(){
    for(int i = 1; i <= 5; i++){
        for(int j = 1; j <= 5; j++){
            cin >> board[i][j];
        }
    }
    
    for(int i = 1; i <= 5; i++){
        for(int j = 1; j <= 5; j++){
            dfs(i, j, board[i][j]);
        }
    }
    
    cout << res;
    return 0;
}