2210번 숫자판 점프

 백트래킹 문제.

 

 중복이 가능하기 때문에 방문 확인 없이 6자리라는 조건만 지키면 된다. 

 

#include <iostream>
#include <string>
#include <map>
#define MAX 6
 
using namespace std;
 
typedef pair<int,int> pir;
int xx[4]={1,0,-1,0};
int yy[4]={0,1,0,-1};
char Num[MAX][MAX];
map<string,int> m;
int ans;
 
void solved(string str, int x, int y){
    
    if(str.size()==6 && m[str]==0){
        m[str]=1;
        ans++;
        return;
    }
    if(str.size()>6) return;
    
    for(int i=0;i<4;i++){
        int nx=x+xx[i];
        int ny=y+yy[i];
        
        if(nx<0 || ny<0 || nx>=5 || ny>=5) continue;
        solved(str+Num[nx][ny], nx, ny);
    }
}
 
int main(){
    
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            cin >> Num[i][j];
        }
    }
 
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            string str="";
            solved(str+Num[i][j], i, j);
        }
    }
    
    cout << ans << endl;
}