uva 10085 10085 - The most distant state

点击打开链接

题目意思： 八数码问题的变形，给定一个初始状态要求找到该状态很够到达的最远的状态，输出这个最远状态和路径。（特判，答案不唯一）

解题思路：  做过八数码的同学肯定觉得这一题很水吧，确实是的，要求我么找到最远的，我么知道广搜是只要有一个节点能够扩展就会继续往下扩展，那么当广搜不能在扩展的时候就是到最远的状态(不理解的可以自己画画图想想)，其它就是八数码的一些注意问题了，见我博客就有详解.

代码：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
using namespace std;
#define MAXN 400000

struct State{
    int state[9];
    int pos;
    char ch[50];
}s[MAXN];
int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
int factor[9] = {1,1,2,6,24,120,720,5040,40320};
int dirtion[4] = {'U','R','D','L'};
int vis[MAXN];
int t , flag;
State star;
queue<int>q;

//哈希函数
int Hash(int s[]){
    int i , j , temp , num;
    num = 0;
    for(i = 0 ; i < 9 ; i++){
        temp = 0;
        for(j = i+1 ; j < 9 ; j++){
            if(s[j] < s[i]) temp++;
        }
        num += factor[8-i]*temp;
    }
    return num;
}

//输出函数
void output(State ans){
    for(int i = 0 ; i < 9 ; i++){
        if(ans.state[i] == 9) printf("0");
        if(ans.state[i] != 9) printf("%d" , ans.state[i]);
        if(i == 2 || i == 5) printf("\n");
        if(i != 2 && i != 5) printf(" ");
    }
    printf("\n");
    for(int i = 0 ; i < strlen(ans.ch) ; i++) printf("%c" , ans.ch[i]);
    printf("\n\n");
} 

//广搜
void Bfs(){
    while(!q.empty()){
        State cur = s[q.front()] ; q.pop();
        int x ,y , c, r;
        flag = 0;
        x = cur.pos/3 ; y = cur.pos%3;
        //printf("%d %d\n" , x , y);
        for(int i = 0 ; i < 4 ; i++){
            r = x + dir[i][0] ; c = y+dir[i][1];
            if(r >=0 && c >= 0 && r < 3 && c < 3){
                State tmp = cur;
                tmp.state[tmp.pos] = tmp.state[r*3+c];
                tmp.pos = r*3+c ; tmp.state[tmp.pos] = 9;

                int hash = Hash(tmp.state);

                if(!vis[hash]){
                    vis[hash] = 1;
                    int len = strlen(tmp.ch);
                    tmp.ch[len]= dirtion[i];
                    s[hash] = tmp;
                    //output(tmp);
                    q.push(hash);
                    flag = 1;
                }
            }
        }
        if(!flag && q.empty()) output(cur);//如果不再扩展说明找到就直接输出
    }
}

int main(){
    //freopen("input.txt" , "r" , stdin);
    scanf("%d%*c" , &t);
    int i , j , n , k , cnt;
    for(cnt = 1 ; cnt <= t ; cnt++){
        k = 0;
        for( i = 0 ; i < 3 ; i++){
            for( j = 0 ; j < 3 ; k++ , j++){
                scanf("%d" , &n);
                star.state[k] = n;
                if(n == 0) { star.state[k] = 9 ; star.pos = i*3+j;}
            }
        }
        while(!q.empty()) q.pop();
        memset(vis , 0 , sizeof(vis));
        int hash = Hash(star.state);
        vis[hash] = 1 ; s[hash] = star;
        q.push(hash);
        printf("Puzzle #%d\n" , cnt);
        Bfs();
    }
    return 0;
}