uva10085 - The most distant state
클래식, 고효율 코드::
#include <cstdio>
#include <cstring>
#define MAX 1000000
int ans, st[MAX][9], head[MAX], next[MAX], posi[MAX], fa[MAX], path[MAX];
int dx[4] = {-1,1,0,0}, dy[4] = {0,0,-1,1};
char dir[4] = {'U','D','L','R'};
int hash(int *A)
{
int v = 0;
for(int i = 0; i < 9; i++) v = v * 10 + A[i];
return v%MAX;
}
int try_to_insert(int s)
{
int h = hash(st[s]);
int u = head[h];
while(u)
{
if(memcmp(st[u], st[s],sizeof(st[s]))==0) return 0;
u = next[u];
}
next[s] = head[h];
head[h] = s;
return 1;
}
void bfs(int p)
{
memset(head,0,sizeof(head));
memset(next,0,sizeof(head));
int rear = 0, front = 1;
posi[0] = p;
try_to_insert(0);
while(rear<front)
{
int x = posi[rear]/3, y = posi[rear]%3;
for(int i = 0; i < 4; i++) if(x+dx[i]>=0&&x+dx[i]<3&&y+dy[i]>=0&&y+dy[i]<3)
{
int op = posi[rear], np = (x+dx[i])*3+y+dy[i];
memcpy(st[front],st[rear],sizeof(st[rear]));
st[front][op] = st[rear][np];
st[front][np] = st[rear][op];
if(try_to_insert(front))
{
posi[front] = (x+dx[i])*3+y+dy[i];
fa[front] = rear;
path[front] = i;
front++;
}
}
rear++;
}
ans = front-1;
}
void print_path(int cur)
{
if(cur)
{
print_path(fa[cur]);
printf("%c",dir[path[cur]]);
}
}
int main ()
{
int t, p, cas = 0;
scanf("%d",&t);
while(t--)
{
for(int i = 0; i < 9; i++) { scanf("%d",&st[0][i]); if(st[0][i]==0) p = i;}
bfs(p);
printf("Puzzle #%d
",++cas);
for(int i = 0; i < 3; i++)
{
printf("%d %d %d", st[ans][3*i], st[ans][3*i+1], st[ans][3*i+2]);
printf("
");
}
print_path(ans);
printf("
");
}
return 0;
}
인코딩 방법도 있어요.그러니까 9 개, 총 9!종류별 배열, 종류별 배열은 모두 번호를 매겨서vis수조로 기록한다...
코드는 다음과 같습니다.
#include <cstdio>
#include <cstring>
#define MAX 800000
int ans, st[MAX][9], vis[362880], posi[MAX], fa[MAX], path[MAX];
int dx[4] = {-1,1,0,0}, dy[4] = {0,0,-1,1}, fact[10] = {1,1,2,6,24,120,720,5040,40320,362880};
char dir[4] = {'U','D','L','R'};
int return_position(int s)
{
int code = 0;
for(int i = 0, u = 0; i < 9; i++)
{
for(int j = i+1; j < 9; j++) if(st[s][i]>st[s][j]) u++;
code+=fact[8-i]*u;
u = 0;
}
return code;
}
void bfs(int p)
{
memset(vis,0,sizeof(vis));
int rear = 0, front = 1;
posi[0] = p;
while(rear<front)
{
int x = posi[rear]/3, y = posi[rear]%3;
for(int i = 0; i < 4; i++) if(x+dx[i]>=0&&x+dx[i]<3&&y+dy[i]>=0&&y+dy[i]<3)
{
int op = posi[rear], np = (x+dx[i])*3+y+dy[i];
memcpy(st[front],st[rear],sizeof(st[rear]));
st[front][op] = st[rear][np];
st[front][np] = st[rear][op];
if(!vis[return_position(front)])
{
vis[return_position(front)] = 1;
posi[front] = (x+dx[i])*3+y+dy[i];
fa[front] = rear;
path[front] = i;
front++;
}
}
rear++;
}
ans = front-1;
}
void print_path(int cur)
{
if(cur)
{
print_path(fa[cur]);
printf("%c",dir[path[cur]]);
}
}
int main ()
{
int t, p, cas = 0;
scanf("%d",&t);
while(t--)
{
for(int i = 0; i < 9; i++) { scanf("%d",&st[0][i]); if(st[0][i]==0) p = i;}
bfs(p);
printf("Puzzle #%d
",++cas);
for(int i = 0; i < 3; i++)
{
printf("%d %d %d", st[ans][3*i], st[ans][3*i+1], st[ans][3*i+2]);
printf("
");
}
print_path(ans);
printf("
");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.