Отримання знань

дистанційна підтримка освіти школярів


Восемь
http://acm.pku.edu.cn/JudgeOnline/problem?id=1077

   Входные данные

   Выходные данные

   Пример входных данных

   Пример выходных данных

   Анализ условия и обсуждение идеи решения

   Примеры решения на C++:

   Решение, базирующееся на двойном поиске в ширину:

#include "iostream" 
#include "string.h"
#include "map"
using namespace std;
map < int,int > hasha,hashb;
const int move[]={1,-1,3,-3};
int can[][9]={{1,1,0,1,1,0,1,1,0},{0,1,1,0,1,1,0,1,1},{1,1,1,1,1,1,0,0,0},{0,0,0,1,1,1,1,1,1}};
int nine[10],ak,sti,bk;
char sts[10]={0},status[10]={0},ch;
char ans[1001];
int st,stx,en,enx=8;
struct que
{
int c,q;
char s[10];
}qa[1000001],qb[1000001];
int ea,eb,ha,hb;
int atoi(char *s)
{
int ret=0,i;
for(i=0; i < 9; i++)ret+=(s[i]-'0')*nine[i];
return ret;
}
void bfs(int &a,int &b)
{
int i;
hasha.clear(),hashb.clear();
ea=eb=2;ha=hb=1;
hasha[st]=1,hashb[en]=1;
strcpy(qa[ea].s,sts),qa[ea].c=stx,qa[ea].q=1;
strcpy(qb[eb].s,"123456780"),qb[eb].c=enx,qb[eb].q=1;
while(ea-ha || eb-hb)
{
if(ea-ha)
{
ha++;
for(i=0; i < 4 ;i++)
{
if(!can[i][qa[ha].c]) continue;
strcpy(status,qa[ha].s);
status[qa[ha].c]=status[qa[ha].c+move[i]];
status[qa[ha].c+move[i]]='0';
sti=atoi(status);
if(!hasha[sti])
{
ea++;
hasha[sti]=ea;
strcpy(qa[ea].s,status);
qa[ea].c=qa[ha].c+move[i];
qa[ea].q=ha;
if(hashb[sti])
{
b=hashb[sti],a=ea;
return;
}
}
}
}
if(eb-hb)
{
hb++;
for(i=0; i < 4; i++)
{
if(!can[i][qb[hb].c]) continue;
strcpy(status,qb[hb].s);
status[qb[hb].c]=status[qb[hb].c+move[i]];
status[qb[hb].c+move[i]]='0';
sti=atoi(status);
if(!hashb[sti])
{
eb++;
hashb[sti]=eb;
strcpy(qb[eb].s,status);
qb[eb].c=qb[hb].c+move[i];
qb[eb].q=hb;
if(hasha[sti])
{
a=hasha[sti],b=eb;
return;
}
}
}
}
}
}
char getccc(int cc)
{
switch(cc)
{
case 1 : return 'r';
case -1: return 'l';
case 3 : return 'd';
case -3: return 'u';
}
}
void solve()
{
int a,b;
st=atoi(sts);
if(en==st)return;
bfs(a,b);
ak=500,bk=501;
while(a-1)
{
ans[ak--]=getccc(qa[a].c-qa[qa[a].q].c);
a=qa[a].q;
}
while(b-1)
{
ans[bk++]=getccc(qb[qb[b].q].c-qb[b].c);
b=qb[b].q;
}
ans[bk-1]=0;
puts(ans+ak+2);
}
int main()
{
int i,j,able=0;
for(i=7,nine[8]=1; i >=0 ;i--)nine[i]=nine[i+1]*9;
en=atoi("123456780");
i=0;
while( i< 9)
{
ch=getchar();
if(isdigit(ch) ||ch=='x')
{
if(ch=='x')stx=i,ch='0';
sts[i]=ch;
i++;
}
}
solve();
return 0;
}

   Решение с использованием хеш-таблицы:

#include "stdio.h" 
#include "string.h"
#define MAXN 362880
const int tar=123456789;
const int pw[10]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
const int jc[10]={1,1,2,6,24,120,720,5040,40320,362880};
int s , st[10] , que[MAXN][3] ;
char ch[50];
bool used[MAXN] ;

bool Isok(){
int i , j , sum ;
sum=0 ;
for (i=1; i < 10; i++)
for (j=i+1; j < 10; j++){
if (st[i] > st[j]) sum++ ;
}
if (sum%2==0) return true ;
return false ;
}
int Init(){
int len , i , q , c=1;
len=strlen(ch);
s=0;
for (i=0; i < len; i++){
if ((ch[i] >= '0' && ch[i]<='9') || ch[i]=='x'){
if (ch[i]=='x') q=c , st[q]=10 ;
else{
if (s==0) s=ch[i]-'0';
else s=s*10+ch[i]-'0' ;
st[c]=ch[i]-'0' ;
c++ ;
}
}
}
memset(used,0,sizeof(used));
s=s*10+q ;
}

int Right(int a ){ return a+1 ;}
int Left (int a){ return a-1 ;}
int Up(int a ){
int t1,t2,t3 ;
t1=9-a%10+1 ;
t2=a/pw[t1] ;
t3=t2/1000*1000+t2%100*10+t2/100%10 ;
return t3*pw[t1]+a%pw[t1]/10*10+a%10-3 ;
}
int Down(int a ){
int t1,t2,t3,t4;
t1=9-a%10+1 ;
t2=a/pw[t1] ;
t3=a%pw[t1];
t4=(t3/pw[t1-2]+t3/pw[t1-3]%10*100)*pw[t1-3]+t3%pw[t1-3] ;
return t2*pw[t1]+t4/10*10+a%10+3 ;
}
int Hash(int a){
int t[9] , i , j , k , res=0;
for (i=0; i < 9; i++) {
t[i]=a/pw[8-i]%10 ;
}
for (i=0; i < 8; i++) {
k=0 ;
for (j=0; j < i; j++)
if (t[i] < t[j]) k++ ;
res+=k*jc[i] ;
}
res+=(9-t[8])*jc[8] ;
return res ;
}
int Solve() {
int tmp , front ,rear ,i , tt;
que[0][0]=s ;
tt=Hash(s);
used[tt]=1 ;
front=0 , rear=1 ;
while(front < rear) {
if (que[front][0] == tar) break;
tmp=(que[front][0]%10-1)%3 ;
if (tmp < 2) {
tmp=Right(que[front][0]);
tt=Hash(tmp);
if (!used[tt]) {
used[tt]=1;
que[rear][0]=tmp ;
que[rear][1]=1 ;
que[rear][2]=front ;
rear++ ;
}
}
tmp=(que[front][0]%10-1)%3 ;
if (tmp > 0) {
tmp=Left(que[front][0]);
tt=Hash(tmp);
if (!used[tt]) {
used[tt]=1;
que[rear][0]=tmp ;
que[rear][1]=2 ;
que[rear][2]=front ;
rear++ ;
}
}
tmp=(que[front][0]%10-1)/3 ;
if (tmp<2) {
tmp=Down(que[front][0]);
tt=Hash(tmp);
if (!used[tt]) {
used[tt]=1;
que[rear][0]=tmp ;
que[rear][1]=4 ;
que[rear][2]=front ;
rear++ ;
}
}
tmp=(que[front][0]%10-1)/3 ;
if (tmp > 0) {
tmp=Up(que[front][0]);
tt=Hash(tmp);
if (!used[tt]) {
used[tt]=1;
que[rear][0]=tmp ;
que[rear][1]=3 ;
que[rear][2]=front ;
rear++ ;
}
}
front++;
}
int stack[MAXN],top=0;
rear=front;
while (rear!=0) {
stack[top++]=que[rear][1];
rear=que[rear][2] ;
}
for (i=top-1; i >= 0; i--) {
switch(stack[i]) {
case 1:putchar('r') ; break;
case 2:putchar('l') ; break;
case 3:putchar('u') ; break;
default:putchar('d');
}
}
printf(" ");
}

int main() {
while (gets(ch)) {
Init();
if(Isok()) {
Solve();
}
else printf("unsolvable ");
}
return 0;
}

 

Попередня Зміст Наступна
В системі: гості - (1); користувачі - (0)