[poj] 2286 The Rotation Game || ID-DFS

原题

有1234四个数字，每个数字八个。有八种方向的移动，使得操作后中间八个方块的数字相同，求最小操作步数。

对于这种求最小步数的看起来就是dfs的题，就ID-DFS就好了。

//不知道为什么都是IDDFS，我的跑的这么慢……

#include<cstdio>

#include<vector>

using namespace std;

int a[30],in[10]={0,7,8,9,12,13,16,17,18},ans,cnt;

int chg[5][8]={{0},{0,1,3,7,12,16,21,23},{0,2,4,9,13,18,22,24},{0,11,10,9,8,7,6,5},{0,20,19,18,17,16,15,14}};

vector <char> v;

char as[10]=" ABCDFEHG";

int read()

{

    int ans=0,fu=1;

    char j=getchar();

    for (;(j<'0' || j>'9') && j!='-';j=getchar()) ;

    if (j=='-') j=getchar(),fu=-1;

    for (;j>='0' && j<='9';j=getchar()) ans*=10,ans+=j-'0';

    return ans*fu;

}

int stp()

{

    int qwq=0,b[5]={0,0,0,0,0};

    for (int i=1;i<=8;i++) b[a[in[i]]]++;

    for (int i=1;i<=4;i++) qwq=max(qwq,b[i]);

    return 8-qwq;

}

bool chk()

{

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

	if (a[in[i]]!=a[in[i+1]]) return 0;

    return 1;

}

void change(int x)

{

    int tmp=a[chg[x][1]];

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

	a[chg[x][i]]=a[chg[x][i+1]];

    a[chg[x][7]]=tmp;

}

void rechange(int x)

{

    int tmp=a[chg[x][7]];

    for (int i=7;i>1;i--)

	a[chg[x][i]]=a[chg[x][i-1]];

    a[chg[x][1]]=tmp;

}

void dfs(int x)

{

    if (ans) return ;

    if (!x)

    {

	if (chk()) ans=1;

	return ;

    }

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

    {

	change(i);

	if (stp()<=x) dfs(x-1);

	if (ans)

	{

	    v.push_back(as[i]);

	    return ;

	}

	rechange(i);

    }

    for (int i=2;i>=1;i--)

    {

	rechange(i);

	if (stp()<=x) dfs(x-1);

	if (ans)

	{

	    v.push_back(as[i+4]);

	    return ;

	}

	change(i);

    }

    for (int i=4;i>2;i--)

    {

	rechange(i);

	if (stp()<=x) dfs(x-1);

	if (ans)

	{

	    v.push_back(as[i+4]);

	    return ;

	}

	change(i);

    }

}

int main()

{

    while (1)

    {

	cnt=0;

	ans=0;

	v.clear();

	a[1]=read();

	if (!a[1]) break;

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

	    a[i]=read();

	if (chk())

	{

	    printf("No moves needed\n%d\n",a[18]);

	    continue;

	}

	while (!ans) dfs(++cnt);

	for (int i=v.size()-1;i>=0;i--) putchar(v[i]);

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

    }

    return 0;

}

巴特西

[poj] 2286 The Rotation Game || ID-DFS

原题

最新文章

热门文章