[SWEA] 2819 격자판의 숫자 이어 붙이기

 

완탐으로 푸는 쉬운 문제다

모든 경우의 수를 생각해도 2^16 인 것 같다

 

모든 위치에서 시작하며 나올 수 있는 수를 모두 set에 넣어보자

마지막에 size를 출력해준다면 그게 곧 답이다!

 

소스코드

#include <iostream>
#include <algorithm>
#include <set>
#include <string>
using namespace std;
char map[5][5];
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};
set<string> s;
 
bool inner(int x,int y){
    return (0<=x && x<4 && 0<=y && y<4);
}
 
void solve(int x,int y,int len,string number){
    if(len==7) {
        s.insert(number); return;
    }
 
    for(int i=0;i<4;i++){
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(inner(nx,ny)){
            solve(nx,ny,len+1,number+map[x][y]);
        }
    }
}
 
int main(){
    //freopen("input.txt","r",stdin);
    int tc; scanf(" %d",&tc); int c=1;
    while(tc--){
        s.clear();
        for(int i=0;i<4;i++){
            for(int j=0;j<4;j++){
                scanf(" %1c",&map[i][j]);
            }
        }
        for(int i=0;i<4;i++){
            for(int j=0;j<4;j++){
                solve(i,j,0,"");
            }
        }
        printf("#%d %d\n",c++,(int)s.size());
    }
}