import java.util.HashSet;
import java.util.Scanner;
public class NumberAttach {
static int[][] map;
static HashSet<String> set;
static int[] dr = {1,0,-1,0};
static int[] dc = {0,1,0,-1};
static int count =0;
public static void main(String args[]) throws Exception
{
Scanner sc = new Scanner(System.in);
int T;
T=sc.nextInt();
for(int test_case = 1; test_case <= T; test_case++)
{
count = 0;
map = new int[4][4];
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
map[i][j] = sc.nextInt();
}
}
set = new HashSet<>();
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
StringBuilder sb = new StringBuilder();
sb.append(map[i][j]);
dfs(i,j,sb);
}
}
System.out.println(set.size());
}
}
public static void dfs(int row, int col,StringBuilder sb){
if(sb.length()==7){
set.add(sb.toString());
return;
}
for (int k = 0; k < 4; k++) {
int nrow = row + dr[k];
int ncol = col + dc[k];
if(nrow<0||ncol<0||nrow>=4||ncol>=4) continue;
sb.append(map[nrow][ncol]);
dfs(nrow,ncol,sb);
sb.delete(sb.length()-1,sb.length());
}
}
}
현재 문자에서 상하좌우 6번 이동해서 지나간 칸을 문자열로 이어붙인다.
1. 현재 좌표의 숫자를 문자열에 추가해주고, 현재 좌표를 dfs탐색한다.
2. 다음 방향을 문자열에 추가해주고 재귀함수 호출한다.
3. 문자열 길이가 7개가 되면 hashSet에 넣어서 중복체크를 해준다.
4. dfs에서 나올때는 이전에 추가한 문자열을 다시 지워준다.
👉Stringbuilder에 int형 자료형을 넣을때는, 자동으로 형변환을 시켜준다.
String에 int형을 넣으려면 String str = 10+""; 이런식으로 추가하자
👉Stringbuilder에 delete 메서드는 시작점부터 끝점의 인덱스 바로 전까지 지운다.
백트래킹의 아주 기본적인 유형의 문제이다.
delete 메서드 인덱스를 잘못 알고 있어서 조금 헤맸다.