Problem C : 루빅의 사각형
제한시간: 1000 ms 메모리제한: 128 MB
Special Judge
4×4 격자판에 1에서 16까지 정수 번호가 매겨진 16개 타일이 임의로 놓여져 있다.
타일을 움직여 그림1과 같이 타일을 놓이게 하려고 한다.
타일을 움직이는 방법은 하나의 행(가로줄)을 오른쪽으로 원하는 칸 수만큼 순환적으로 움직이거나,
하나의 열(세로줄)을 원하는 칸 수만큼 아래쪽으로 순환적으로 움직이는 것이다.
그림 2는 그림 1의 2번째 행을 오른쪽으로 2칸 움직인 것이다.
그림 1의 2번째 행의 오른쪽 끝에 있는 7번 타일과 8번 타일이 오른쪽 경계를 넘어가서 왼쪽 끝으로 옮겨갔다.
그림 3은 그림 2의 3번째 열을 아래쪽으로 1칸 움직인 것이다.
그림 2의 3번째열의 가장 아래에 있는 15번 타일이 가장위쪽으로 옮겨갔다.
그림 3과 같이 타일이 놓여진 격자판이 주어졌다면 3번째 열을 3칸 움직인 다음,
2번째 행을 2칸 움직이면 그림 1과 같이 타일이 놓이게 된다.
따라서 2번 움직이면 된다.
1에서 16까지 번호가 매겨진 타일이 임의로 놓여져 있을 때 그림 1과 같이 타일이 놓일 수 있도록
타일을 움직이는 순서를 출력하는 프로그램을 작성하시오. 여기서 움직이는 횟수는 최소로 하여야 한다.
4×4 격자판에 놓여진 타일 번호가 행단위로 4개 줄에 주어진다. 타일 번호는 1부터 16까지의 정수이다. 각 줄에는 해당하는 행에 놓여지는 4개타일의 번호가 빈칸을 사이에 두고 순서대로 주어진다.
첫 번째 줄에는 움직이는 횟수를, 두 번째 줄부터는 한 줄에 하나씩 타일을 움직이는 방법을 순서대로 출력한다. 이 때, 격자판의 i번째 행을 k칸 움직였다면 정수 1과 i와 k를 빈칸을 사이에 두고 한 줄에 출력한다. 그리고 격자판의 i번째 열을k칸 움직였다면 정수2와 i와k를 빈칸을 사이에 두고 한 줄에 출력한다. 여기서 i는 1 이상 4 이하, k는 1 이상3이하의 정수이다. *주의 사항 앞에서 설명한 방법에 따라 한 행 또는 한 열의 타일을 움직이는 것은 움직이는 칸수와 관계없이 한 번으로 간주한다. 주어진 모든 입력은 최소 1번 최대 7번 타일을 움직이면 그림 1과 같이 타일이놓이게 할 수 있다.
1 2 15 4
7 8 3 6
9 10 5 12
13 14 11 16
2
2 3 3
1 2 2
#include <stdio.h>
int tile[6][6], ans = 8;
struct data {
int rc, num, cnt;
} moving[10], moveans[10];
int okcnt()
{
int cnt = 0;
for (int i = 1, k = 1; i <= 4; i++)
for (int j = 1; j <= 4; j++)
cnt += tile[i][j] == k++;
return cnt;
}
void rotate(int rc, int num) // 방향과 횟수 입력 받아서 돌리기
{
int tmp, i;
if (rc == 1) {
tmp = tile[num][4];
for (i = 4; i > 1; i--) tile[num][i] = tile[num][i - 1];
tile[num][1] = tmp;
}
else {
tmp = tile[4][num];
for (i = 4; i > 1; i--) tile[i][num] = tile[i - 1][num];
tile[1][num] = tmp;
}
}
void dfs(int step)
{
int ok = okcnt(), i, j, k; // 기존 16개와 동일한 cnt 갯수세기
if (ok == 16) { // 정답과 동일 하다면
ans = step; // ans는 step 입력받음 // 기존 정답과 비교 < 해야하지 않남
for (i = 0; i < ans; i++) moveans[i] = moving[i];
return;
}
if (ok < (step + 5 - ans) * 4) return; // 가지치기
for (i = 1; i <= 2; i++) { // 오른쪽, 아래로 돌아가면서 돌리기
for (j = 1; j <= 4; j++) {
for (k = 1; k < 4; k++) {
moving[step] = { i, j, k }; // 어떻게 돌렸는지 저장
rotate(i, j);
dfs(step + 1); // 스텝 + 해서 다시 dfs로 들어감
}
rotate(i, j); // 다시 되돌리기 dfs 체크 사항
}
}
}
int main()
{
freopen("input.txt", "r", stdin);
for (int i = 1; i <= 4; i++)
for (int j = 1; j <= 4; j++)
scanf("%d", &tile[i][j]);
dfs(0);
printf("%d\n", ans);
for (int i = 0; i < ans; i++)
printf("%d %d %d\n", moveans[i].rc, moveans[i].num, moveans[i].cnt);
return 0;
}
'Computer Science' 카테고리의 다른 글
Problem A : 수열 (0) | 2020.01.07 |
---|---|
큐브 (0) | 2020.01.07 |
CPP OOP 유력문제 (0) | 2019.07.18 |
컴퓨터실 (0) | 2019.06.11 |
protocol (0) | 2019.05.17 |
댓글