티스토리 뷰
완탐으로 푸는 쉬운 문제다
모든 경우의 수를 생각해도 2^16 인 것 같다
모든 위치에서 시작하며 나올 수 있는 수를 모두 set에 넣어보자
마지막에 size를 출력해준다면 그게 곧 답이다!
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
#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());
}
}
|
'알고리즘 > SW Expert Academy' 카테고리의 다른 글
[SWEA] 1824 혁진이의 프로그램 검증 (0) | 2020.01.12 |
---|---|
[SWEA] 9232 한길이의 생일 선물 (0) | 2020.01.12 |
[SWEA] 3752 가능한 시험 점수 (0) | 2020.01.12 |
[SWEA] 1249 보급로 (0) | 2020.01.11 |
[SWEA] 4112 이상한 피라미드 탐험 (0) | 2020.01.11 |
댓글