Poj 1184 聪明的打字员 (搜索)

左手的ㄟ右手 2023-01-05 03:55 104阅读 0赞

目前依旧不明觉厉……贴代码留待以后理解，以下是参考链接

思路:http://wenku.baidu.com/view/0c2742fb770bf78a65295406.html  
代码:http://hi.baidu.com/kmzchchycfdeovr/item/6d7358b32be4edf762388eb6

2015-4-27更新：由于百度空间即将关闭，故将提到的参考文章复制到了下面。

三个多月了，哥今天终于A了你了，嘿嘿……这题靠普通的广搜是过不了的，状态数有10^6种，不剪枝显然TLE。

那怎么做呢。我们先把这6种操作分成两类：一类是移动光标，交换数字的；另一类则是改变数字大小的。我们先对第一类操作预处理，计算出任意一种数字排列方法要操作多少次，然后计算这种排列要改变数字多少次。不过还有一点，就是算某种数字排列方法时，还要把光标经过哪些数字算出来，因为如果不经过某些数字的话，改数字是无法改变大小的。这样就把状态压倒13000多种。110MS能过。但是还能优化，分析发现，向左移这个操作是没有用的。因为向左移的数字都是光标已经经过的数字，如果要交换或改变大小的话，大可在经过这个数字的时候就做，没必要又把光标移回去。去了个操作，状态就只有500多种了。这样只要16MS了。

#include <cstdio>
    #include <cstring>
    #include <queue>
    using namespace std;
    
    struct Node
    {
        int s[6];
        int sum,cursor,sign;
    };
    
    int ans[532][8],total = 0;
    bool visited[6][6][6][6][6][6][6][10];
    
    int sign[10][6] = { {1,0,0,0,0,0},
                        {1,1,0,0,0,0},
                        {1,1,1,0,0,0},
                        {1,1,1,1,0,0},
                        {1,1,1,1,1,0},
                        {1,1,1,1,1,1},
                        {1,0,0,0,0,1},
                        {1,1,0,0,0,1},
                        {1,1,1,0,0,1},
                        {1,1,1,1,0,1},
                       };
    
    void BFS ()
    {
    	Node a;
    	int i;
    	for (i=0;i<6;i++)
    		a.s[i]=i;
    	a.sum = 0;a.cursor = 0;a.sign = 0;
    	queue<Node> q;
    	q.push(a);
    	visited[a.s[0]][a.s[1]][a.s[2]][a.s[3]][a.s[4]][a.s[5]][a.cursor][a.sign]=true;
    	while (!q.empty())
    	{
    		a=q.front();
    		q.pop();
    		for (i=0;i<6;i++)
    			ans[total][i] = a.s[i];
            ans[total][6] = a.sign;
    		ans[total][7] = a.sum;
            total++;
            a.sum++;
            if (a.cursor > 0)
            {
                swap(a.s[a.cursor],a.s[0]);
                if (visited[a.s[0]][a.s[1]][a.s[2]][a.s[3]][a.s[4]][a.s[5]][a.cursor][a.sign]==false)
                {
                    q.push(a);
                    visited[a.s[0]][a.s[1]][a.s[2]][a.s[3]][a.s[4]][a.s[5]][a.cursor][a.sign] = true;
                }
                swap(a.s[a.cursor],a.s[0]);
            }
            if (a.cursor < 5)
            {
                a.cursor++;
                int temp = a.sign;
                if (a.cursor > a.sign || (a.cursor > a.sign - 6 && a.sign > 5))
                {
                    if (a.sign == 9)
                        a.sign = 5;
                    else
                        a.sign++;
                }
                if (visited[a.s[0]][a.s[1]][a.s[2]][a.s[3]][a.s[4]][a.s[5]][a.cursor][a.sign]==false)
                {
                    q.push(a);
                    visited[a.s[0]][a.s[1]][a.s[2]][a.s[3]][a.s[4]][a.s[5]][a.cursor][a.sign] = true;
                }
                a.cursor--;
                a.sign = temp;
                if (a.sign < 5)
                    a.sign += 6;
                swap (a.s[a.cursor],a.s[5]);
                if (visited[a.s[0]][a.s[1]][a.s[2]][a.s[3]][a.s[4]][a.s[5]][a.cursor][a.sign]==false)
                {
                    q.push(a);
                    visited[a.s[0]][a.s[1]][a.s[2]][a.s[3]][a.s[4]][a.s[5]][a.cursor][a.sign] = true;
                }
            }
        }
    }
    
    int main ()
    {
    	int res=0x3fffffff,i,j,a[6],b[6];
    	BFS ();
    	for (i=0;i<6;i++)
    		scanf("%1d",&a[i]);
    	for (i=0;i<6;i++)
    		scanf("%1d",&b[i]);
    	for (i=0;i<total;i++)
    	{
    		int step = ans[i][7];
    		for (j=0;j<6;j++)
    			if (a[ans[i][j]] != b[j] && !sign[ans[i][6]][j])
    				break;
    			else
    				step += abs(a[ans[i][j]] - b[j]);
    		if (j==6 && res>step)
    			res=step;
    	}
    	printf("%d\n",res);
    	return 0;  
    }