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

초기화좀 잘하자.. 테케 많이 받잖아..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7I5fgqEogDFAXB 

SW Expert Academy

#include <cstdio>
#include <cstring>
#include <string>
#include <set>
int T;
int board[4 + 2][4 + 2];

std::set<std::string> S;

void input()
{
	// init
	memset(board, 0, sizeof(board));
	S.clear();


	for (int r = 0; r < 4; r++) {
		for (int c = 0; c < 4; c++) {
			scanf("%d", &board[r][c]);
		}
	}
}


void DFS(int x, int y, std::string now)
{
	// dir 
	static int dir_x[4] = { 0, 0, 1, -1 };
	static int dir_y[4] = { 1, -1, 0, 0 };

	if (now.size() == 7) {
		S.insert(now);
		return;
	}

	for (int p = 0; p < 4; p++) {
		int nx = x + dir_x[p];
		int ny = y + dir_y[p];

		if (nx < 0 || nx > 4 - 1 || ny < 0 || ny > 4 - 1) continue;
		std::string backup = now;
		now += (board[nx][ny] + '0');
		DFS(nx, ny, now);
		now = backup;
	}

}

void Search()
{
	for (int r = 0; r < 4; r++) {
		for (int c = 0; c < 4; c++) {
			std::string curr = "";
			curr += (board[r][c] + '0');
			DFS(r, c, curr);
		}
	}
}



int main()
{
	scanf("%d", &T);
	for (int t = 1; t <= T; t++) {
		input();
		Search();
		printf("#%d %d\n", t, S.size());
	}
	return 0;
}

(0, 0)부터 (3, 3) 까지 시작점으로 두고 완전탐색한다. 

해당 칸의 숫자는 DFS 파라미터인 now에 계속 추가하고, 만약 now.size() == 7이 되면 시작점으로부터 6칸 움직여서 7자리 숫자를 만든것이므로 set S에 insert 해준다. (중복 방지)

마지막에는 S의 사이즈만 출력해주면 된다.