每一块砖头只有两种形状，而且位置情况最多只有5中，数量最多有24个。。。

所以可以用一个longlongint来把所有的砖块位置存下来。。。。然后暴力bfs还能跑100ms

Unblock Me

Unblock Me is a simple and addictive puzzle game on iPhone/iPod Touch. The goal is to get the red block out of the board by sliding the other blocks out of the way.

You can only move the block if it has a free space to move. In one step, you can move only one block, and you can move multiple units. To clear the puzzle, you have to move the red block out of the board. The red block can only move in horizontal direction. The vertical blocks can move in vertical direction only. The horizontal blocks can move in horizontal direction only.
Now try to crack it. The board is 6*6. There are two kinds of vertical blocks (1*2, 1*3), and two kinds of horizontal blocks (2*1, 3*1). The exit is always at the right of the grid (5, 2).

12
0 0 1 0 2
1 1 0 1 1
2 2 0 2 1
3 3 0 5 0
4 1 2 2 2
5 3 1 3 2
6 4 1 4 2
7 5 1 5 3
8 0 3 1 3
9 2 3 3 3
10 4 3 4 4
11 0 4 0 5
4

16

Hint
See the image below to get more details.
 
 
 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <queue>

using namespace std;

typedef long long int LL;
typedef pair<LL,int> LD;

struct BLOCK
{
    int t,l,c;
}B[30];

int N,R;
LL S;
bool tu[10][10];

set<LL> vis;

bool check(LL s)
{
    int val=(s&(7LL<<(R*3)))>>(R*3);
    if(val+B[R].l==6) return true;
    return false;
}

void buildtu(LL S,int x)
{
    memset(tu,0,sizeof(tu));
    for(int i=0;i<N;i++)
    {
        if(i==x) continue;
        int valu=(S&(7LL<<(i*3)))>>(i*3);
        for(int j=0;j<B[i].l;j++)
        {
            if(B[i].t==0) tu[B[i].c][valu+j]=1;
            else tu[valu+j][B[i].c]=1;
        }
    }
}

bool isOK(int v,int x)
{
    if(v+B[x].l>6) return false;
    for(int i=0;i<B[x].l;i++)
    {
        if(B[x].t==0)
        {
            if(tu[B[x].c][v+i])
               return false;
        }
        else
        {
            if(tu[v+i][B[x].c])
                return false;
        }
    }
    return true;
}

LL changeS(LL S,int x,int p)
{
    S&=~((7LL)<<(x*3));
    S|=((LL)p<<(x*3));
    return S;
}

int bfs(LL S)
{
    vis.clear();
    vis.insert(S);
    queue<LD> q;
    q.push(make_pair(S,0));

    while(!q.empty())
    {
        LD u,v;
        u=q.front(); q.pop();
        if(check(u.first))
        {
            if(u.second==0) u.second=1;
            return u.second;
        }
        for(int i=0;i<N;i++)
        {
            int valu=(u.first&(7LL<<(i*3)))>>(i*3);
            buildtu(u.first,i);
            for(int j=valu+1;j+B[i].l<=6;j++)
            {
                if(isOK(j,i))
                {
                    LL SE=changeS(u.first,i,j);
                    if(vis.count(SE)) continue;
                    vis.insert(SE);
                    q.push(make_pair(SE,u.second+1));
                }
                else break;
            }
            for(int j=valu-1;j>=0;j--)
            {
                 if(isOK(j,i))
                {
                    LL SE=changeS(u.first,i,j);
                    if(vis.count(SE)) continue;
                    vis.insert(SE);
                    q.push(make_pair(SE,u.second+1));
                }
                else break;
            }
        }
    }
    return -1;
}

int main()
{
while(scanf("%d",&N)!=EOF)
{
    S=0;
    for(int i=0;i<N;i++)
    {
        int x1,y1,x2,y2;
        scanf("%*d%d%d%d%d",&x1,&y1,&x2,&y2);
        if(x1==x2)
        {
            B[i].t=0;
            B[i].l=y2-y1+1;
            B[i].c=x1;
            S|=((LL)y1<<(i*3));
        }
        else if(y1==y2)
        {
            B[i].t=1;
            B[i].l=x2-x1+1;
            B[i].c=y2;
            S|=((LL)x1<<(i*3));
        }
    }
    scanf("%d",&R);

    printf("%d\n",bfs(S));
}
    return 0;
}

HDOJ 3900 Unblock Me

原文：http://blog.csdn.net/u012797220/article/details/19804361