uva10085

この問題は8符号化の問題と少し似ていますが、目標状態を求めるのではなく、達成できる最も遠い図を求めています.
考え方:
初めてこのような問題に触れて、問題解を見てやっと過ぎた.ハッシュ判定とbfsを用い,再帰的な印刷経路も必要である.

#include <iostream>
using namespace std;
#include <cstring>
#include <stdio.h>

typedef int State[9];
const int MAXSTATE = 1000000;
int state[9];
State st[MAXSTATE],goal;
int father[MAXSTATE],path[MAXSTATE],ans;
char path_dir[5] ="UDLR";
int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};

const int MAXHASHSIZE = 1000003;
int head[MAXHASHSIZE],next1[MAXSTATE];

void init_lookup_table () {
    memset(head,0,sizeof(head));
}
int hash1(State &s );
int try_to_insert(int s) {
    int h = hash1(st[s]);
    int u = head[h];
    while(u) {
        if(memcmp(st[u],st[s],sizeof(st[s])) == 0) return 0;
        u = next1[u];
    }
    next1[s] = head[h];
    head[h] = s;
    return 1;
}

void bfs() {
    init_lookup_table();
    father[0] = path[0] =-1;
    int front = 0 ,rear =1;
    memcpy(st[0],state,sizeof(state));
    try_to_insert(0);

    while(front < rear) {
        int *s =st[front];

        int j;
        for(j = 0; j <9; j++)
            if(!s[j])
                break;
        int x = j/3,y = j%3;
        for(int i = 0 ; i <4; i++) {
            int dx = x+ dir[i][0];
            int dy = y + dir[i][1];
            int pos = dx * 3 + dy;

            if(dx >= 0 && dx <3 && dy >=0 && dy <3) {
                int *newState = st[rear];
                memcpy(newState,s,sizeof(int)*9);
                newState[j] = s[pos];
                newState[pos] = 0;
                if(try_to_insert(rear)) {
                    father[rear] = front;
                    path[rear] = i;
                    rear++;
                }
            }
        }
        front ++;
    }
    ans = rear -1;
}

int hash1(State &s) {
    int v = 0;
    for(int i = 0; i <9 ;i++)
        v = v * 10 + s[i];
    return v% MAXHASHSIZE;
}

void print_path(int cur) {
    if(cur!= 0) {
        print_path(father[cur]);
        printf("%c",path_dir[path[cur]]);
    }
}

int main() {

    int T,cas = 1;
    scanf("%d",&T);
    while(T--) {
        for(int i = 0; i < 9; i++)
            scanf("%d",&state[i]);
        bfs();
        printf("Puzzle #%d
",cas++);
        for(int i = 0; i <3; i++)
            printf("%d %d %d
",st[ans][i*3],st[ans][i*3+1],st[ans][i*3+2]);
        print_path(ans);
        printf("

");
    }

    return 0;
}