G - The Rotation Game UVA - 1343

题意：

有8个一，8个2，8个三。有A-H个操作，每种操作往相应方向移动数字（第一个数字移到最后一位），求使得中间数字相同的最小操作步数的方案。

题解：

8^n直接搜索会超时，肯定需要剪枝。这题用到IDA*算法，在搜索的时候假设一个最大步数，然后计算当前到达最终状态的所需最小步数，当当前走的步数加上所需的最小步数都比我们假定的最大步数大的时候就回溯。

#include <bits/stdc++.h>
using namespace std;
/*
      00    01
      02    03
04 05 06 07 08 09 10
      11    12
13 14 15 16 17 18 19
      20    21
      22    23
*/
int line[8][7] = {
        0,2,6,11,15,20,22,      //A
        1,3,8,12,17,21,23,      //B
        10,9,8,7,6,5,4,         //C
        19,18,17,16,15,14,13,    //D
        23,21,17,12,8,3,1,      //E
        22,20,15,11,6,2,0,      //F
        13,14,15,16,17,18,19,    //G
        4,5,6,7,8,9,10          //H
};
int maxd;
int center[8] = {6,7,8,12,17,16,15,11};
int reve[8] = {5,4,7,6,1,0,3,2};
int a[24];
char s[1010];
bool finish()
{
    for(int i = 0;i < 8;i++)
    {
        if(a[center[i]] != a[center[0]])
            return false;
    }
    return true;
}
int dif(int x)
{
    int res = 0;
    for(int i = 0;i < 8;i++)
    {
        if(a[center[i]] != x) res++;
    }
    return res;
}
int mind()
{
    return min(min(dif(1),dif(2)),dif(3));
}
void mov(int i)
{
    int temp = a[line[i][0]];
    for(int j = 0;j < 6;j++)
    {
        a[line[i][j]] = a[line[i][j + 1]];
    }
    a[line[i][6]] = temp;
}
bool dfs(int d,int maxd)
{
    if(finish())
    {
        s[d] = '\0';
        printf("%s\n",s);
        return true;
    }
    if(d + mind() > maxd) return false;    //关键步骤 剪枝
    for(int i = 0;i < 8;i++)
    {
        s[d] = 'A' + i;
        mov(i);
        if(dfs(d + 1,maxd)) return true;
        mov(reve[i]);
    }
    return false;
}
int main()
{
    while(scanf("%d",&a[0]) && a[0])
    {
        for(int i = 1;i < 24;i++)
        {
            scanf("%d",&a[i]);
        }
        if(finish())
        {
            printf("No moves needed\n");
            printf("%d\n",a[6]);
            continue;
        }
        for(maxd = 1;;maxd++)
        {
            if(dfs(0,maxd)) break;
        }
        printf("%d\n",a[6]);
    }
    return 0;
}

H - Lattice Animals UVA - 1602

题意：

给出n个方块，长w宽h的方格图，问最多能放多少不同的由n个方块组成的连通块。可以通过旋转，平移，翻转得到的视为同一种。

题解：

首先是如何表示一种方块组合形式。可以用一个（x,y）坐标来表示一个方块的位置，那么一组这样的坐标就可以表示一种连通块了。
对于平移可以得到的连通块，可以把连通块标准化，以连通块最左上角的方块为原点更新其他方块的坐标。
顺时针旋转90度可以用(x = y,y = -x)来表示，翻转可以用(x = x,y = -y)来表示。
然后再从1个方格到10个方格逐步添加方格再去重，再打出n从1到10的表。
思路比较简单，但是非常难写。

#include <bits/stdc++.h>
using namespace std;
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
struct cell               //单个格子
{
    int x,y;
    cell(int _x,int _y)
    {
        x = _x;
        y = _y;
    }
    bool operator < (const cell& rhs)const
    {
        if(x == rhs.x)
            return y < rhs.y;
        return x < rhs.x;
    }
};
typedef set<cell>block;   //一个连通块
block normal(block b)    //标准化连通块
{
    set<cell>::iterator it;
    int minx = b.begin()->x,miny = b.begin()->y;
    for(it = b.begin();it != b.end();it++)
    {
        minx = min(minx,it->x);
        miny = min(miny,it->y);
    }
    block b1;
    for(it = b.begin();it != b.end();it++)
    {
        b1.insert(cell(it->x - minx,it->y - miny));
    }
    return b1;
}
block rota(block b)     //旋转连通块
{
    set<cell>::iterator it;
    block b1;
    for(it = b.begin();it != b.end();it++)
    {
        b1.insert(cell(it->y,-it->x));
    }
    return normal(b1);
}
block flip(block b)   //以x为轴翻转连通块
{
    set<cell>::iterator it;
    block b1;
    for(it = b.begin();it != b.end();it++)
    {
        b1.insert(cell(it->x,-it->y));
    }
    return normal(b1);
}
set<block>num[15];          //方块个数为i的连通块集合
void check(block b,cell c)  //去重
{
    block bb = b;
    bb.insert(c);
    bb = normal(bb);
    int n = bb.size();
    for(int i = 0;i < 4;i++)
    {
        if(num[n].count(bb) != 0) return;
        bb = rota(bb);
    }
    bb = flip(bb);
    for(int i = 0;i < 4;i++)
    {
        if(num[n].count(bb) != 0) return;
        bb = rota(bb);
    }
    num[n].insert(bb);
}
void dfs()
{
    set<cell>::iterator it;
    set<block>::iterator itt;
    block b;
    b.insert(cell(0,0));
    num[1].insert(b);
    for(int i = 2;i <= 10;i++)
    {
        for(itt = num[i - 1].begin();itt != num[i - 1].end();itt++)
        {
            for(it = (itt)->begin();it != (itt)->end();it++)
            {
                for(int j = 0;j < 4;j++)        //枚举下一个方块位置
                {
                    cell newb(it->x + dx[j],it->y + dy[j]);
                    if(itt->count(newb) == 0)
                    {
                        check(*itt,newb);
                    }
                }
            }
        }
    }
}
int ans[15][15][15];
void table()
{
    set<cell>::iterator it;
    set<block>::iterator itt;
    for(int i = 1;i <= 10;i++)
    {
        for(int j = 1;j <= 10;j++)
        {
            for(int k = 1;k <= 10;k++)
            {
                int cnt = 0;
                for(itt = num[i].begin();itt != num[i].end();itt++)
                {
                    int maxx = 0,maxy = 0;
                    for(it = itt->begin();it != itt->end();it++)
                    {
                        maxx = max(maxx,it->x);
                        maxy = max(maxy,it->y);
                    }
                    if(min(maxx,maxy) < min(j,k) && max(maxx,maxy) < max(j,k)) cnt++;
                }
                ans[i][j][k] = cnt;
            }
        }
    }
}
int main()
{
    dfs();
    table();
    int n,w,h;
    while(scanf("%d %d %d",&n,&w,&h) != EOF)
    {
        printf("%d\n",ans[n][w][h]);
    }
    return 0;
}