7-12 The Rotation Game IDA*

状态搜索题目  一开始打算用bfs  但是图给的不是矩形图  有点难以下手

参考了 lrj    将图上所有的点进行标号  直接一个一维数组就解决了图的问题  并且明确了每个点的标号  处理起来十分方便   可见处理不规则图一定要标号解决   之前的万圣节的早晨也是进行标号处理

用IDA* 十分快

启发方程为  d+h（）<maxx   显然一次变动最多只改变了中心的一个格子  最多使得 多一个数字填充完毕

很有价值的状态搜索题目

#include<bits/stdc++.h>

using namespace std;

#define N 1000

int a[];

int rev[]={,,,,,,,};

int center[]={,,,,,,,};

int line[][]={

  { , , ,,,,}, // A

  { , , ,,,,}, // B

  {, , , , , , }, // C

  {,,,,,,}, // D

};

int judge(void)

{

    for(int i=;i<;i++)

      if(a[ center[i] ]!=a[ center[] ])return ;

    return ;

}

void change(int x)

{

    int temp=a[ line[x][] ];

    for(int i=;i<;i++)

      a[ line[x][i] ]=a[ line[x][i+] ];

      a[ line[x][] ]=temp;

}

int differ(int x)

{

    int n=;

    for(int i=;i<;i++)

      if(a[ center[i] ]!=x)n++;

      return n;

}

int h(void)

{

    return min(differ(),min(differ(),differ()));

}

char ans[N];

bool dfs(int d,int maxx)

{

    if(judge())

    {

        ans[d]='\0';

        printf("%s\n",ans);

        return true;

    }

    if( d+h() >maxx)return false;

    for(int i=;i<;i++)

    {

        ans[d]=i+'A';

        change(i);

        if(dfs(d+,maxx))return true;

        change( rev[i] );

    }

  return false;

}

void solve(void)

{

    if(judge()){printf("No moves needed\n");}

    else

        for(int maxx=;;maxx++)

        if(dfs(,maxx))break;

    printf("%d\n",a[]);

    return ;

}

int main()

{

    for(int i=;i<=;i++)

        for(int j=;j<;j++)

           line[i][j]= line[ rev[i] ][-j];

    while(scanf("%d",&a[]),a[])

    {

        for(int i=;i<=;i++)scanf("%d",&a[i]);

        solve();

    }

}