uva 10085 - The most distant state
The Most Distant State
Input: standard input
Output: standard output
The 8-puzzle is a square tray in which eight square tiles are placed. The remaining ninth square is uncovered. Each tile has a number on it. A tile that is adjacent to the blank space can be slid into that space. A game consists of a starting state and a specified goal state. The starting state can be transformed into the goal state by sliding (moving) the tiles around. The 8-puzzle problem asks you to do the transformation in minimum number of moves.
이
팔
삼
일
이
삼
일
육
사
=>
팔
사
칠
오
칠
육
오
Start
Goal
However, our current problem is a bit different. In this problem, given an initial state of the puzzle your are asked to discover a goal state which is the most distant (in terms of number of moves) of all the states reachable from the given state.
Input
The first line of the input file contains an integer representing the number of test cases to follow. A blank line follows this line.
Each test case consists of 3 lines of 3 integers each representing the initial state of the puzzle. The blank space is represented by a 0 (zero). A blank line follows each test case.
Output
For each test case first output the puzzle number. The next 3 lines will contain 3 integers each representing one of the most distant states reachable from the given state. The next line will contain the shortest sequence of moves that will transform the given state to that state. The move is actually the movement of the blank space represented by four directions : U (Up), L (Left), D (Down) and R (Right). After each test case output an empty line.
Sample Input
1 2 6 4 1 3 7 0 5 8
Sample Output
Puzzle #1 8 1 5 7 3 6 4 0 2 UURDDRULLURRDLLDRRULULDDRUULDDR
시작 상태(이미 알고 있음)에서 목표 상태(미지)까지 이동 횟수가 가능한 한 많아야 한다. 물론 반복해서 이동할 수 없기 때문에 무게를 판정해야 한다. 효율적인 알고리즘을 생각하지 못하고 이동할 수 있는 것만 구한다. 그러면 마지막으로 이동하지 못하는 것은 자연 목표 상태이다. 그의 이동 횟수는 반드시 가장 많고 bfs는 모든 상태를 제시한다.전체 배열의 해시를 중용하는 판결을 내렸습니다. 상태 수가 너무 많습니다. bfs는 반복적으로 호출되어 창고가 넘칠 것 같습니다.
#include<string.h>
#include<stdio.h>
#define P for (i=0;i<9;i++){printf("%d",q[top].a[i]);if ((i+1)%3==0) printf("
");else printf(" ");}
struct node
{int a[9],x,y,succ,dir;
}q[362881];
int top,tail,visit[362881],exp[8]={40320,5040,720,120,24,6,2,1},
move[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int s[1000];
int hash(struct node *A,int num )//
{int i,j,x,y=0;
for (i=0;i<9;i++)
{
x=0;
for (j=i+1;j<9;j++)
if (q[num].a[i]>q[num].a[j]) ++x; //
y=y+x*exp[i];
}
return y;
}
int main()
{begin
int i,j,k,t,T,px,py,pk,sum,temp;
scanf("%d",&T);
for (t=1;t<=T;t++)
{
memset(visit,0,sizeof(visit));
for (i=0;i<9;i++)
{
scanf("%d",&q[0].a[i]);
if (q[0].a[i]==0) {q[0].x=i/3;q[0].y=i%3;}
}
top=0; tail=0;
visit[hash(&q[0],0)]=1;
while (top<=tail)
{
for (i=0;i<4;i++)
{
px=q[top].x+move[i][0];
py=q[top].y+move[i][1];
if ((px>=0)&&(py>=0)&&(px<3)&&(py<3))
{
k=q[top].x*3+q[top].y;
pk=px*3+py;
++tail;
for (j=0;j<9;j++)
q[tail].a[j]=q[top].a[j];
temp=q[tail].a[k]; q[tail].a[k]=q[tail].a[pk]; q[tail].a[pk]=temp;
k=hash(&q[tail],tail);
if (visit[k]) --tail;
else {visit[k]=1;q[tail].succ=top; q[tail].dir=i;q[tail].x=px;q[tail].y=py;}
}
}
++top;
}
--top;
printf("Puzzle #%d
",t);P;
sum=0;
while (top)
{
s[++sum]=q[top].dir;
top=q[top].succ;
}
for (i=sum;i>=1;i--)
{
if (s[i]==0) printf("U");
if (s[i]==1) printf("D");
if (s[i]==2) printf("L");
if (s[i]==3) printf("R");
}
printf("
");
}
end;
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Ruby의 구조체 클래스은 접근자 메서드가 있는 속성 모음입니다. 클래스를 명시적으로 작성할 필요 없이. Struct 클래스는 구성원 및 해당 값 집합을 포함하는 새 하위 클래스를 생성합니다. 각 멤버에 대해 #attr_accessor 와...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.