首页 > 搜索 > BFS搜索 > HDU 3900-Unblock Me-BFS-[解题报告]HOJ
2015
04-14

HDU 3900-Unblock Me-BFS-[解题报告]HOJ

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.
JLUCPC

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).
JLUCPC

输入:

There are several cases in the input data.
For each case:
The first line contains a number N which indicates how many blocks are on the board, then N lines follows. Each line contains five numbers. The first number is the index of this block, which increase from 0 to N-1. The next two numbers is the coordinate of the left upper corner. The last two numbers is the coordinate of the right down corner.
The last line contains one number which is the red block’s index.

输出:

There are several cases in the input data.
For each case:
The first line contains a number N which indicates how many blocks are on the board, then N lines follows. Each line contains five numbers. The first number is the index of this block, which increase from 0 to N-1. The next two numbers is the coordinate of the left upper corner. The last two numbers is the coordinate of the right down corner.
The last line contains one number which is the red block’s index.

样例输入:

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.
JLUCPC
JLUCPC

http://acm.hdu.edu.cn/showproblem.php?pid=3900

状压BFS。。。

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define ll long long
struct data
{
    int t,l,c;  ///t---type 0:heng 1:shu    l:length
}B[3545];       ///c:weizhi
int n,r;    ///red block
#include<map>
#include<queue>
#include<set>
map<ll,bool > vis;
ll s;
inline bool check(ll s,int x)   /// Xth block
{
    int tx=(s&(7ll<<(x*3)))>>(x*3);
    for(int i=0;i<n;i++)
    {
        if(i==x) continue;
        int ti=(s&(7ll<<(i*3)))>>(i*3);
        if(B[x].t==B[i].t) {
            if(B[x].c!=B[i].c) continue;
            if(tx+B[x].l<=ti||ti+B[i].l<=tx) continue;
            return 0;
        } else {
            if(tx+B[x].l>B[i].c&&B[i].c>=tx&&
               ti<=B[x].c&&B[x].c<B[i].l+ti) {
                return 0;
            }
        }
    }
    return 1;
}
inline bool done(ll s)
{
    for(int i=0;i<n;i++) {
        if(B[i].t==1) continue;
        int tt= ((s&(7ll<<(3*r)))>>(r*3));
        if(B[i].c<tt+B[r].l) continue;
        int l=((s&(7ll<<(3*i)))>>(i*3)) , r=l+B[i].l;
        if(r<=2||l>2) continue;
        return 0;
    }
    return 1;
}
inline void cover(ll& s,int x,int p)
{
    s&=~(7ll<<(x*3));
    s|=(ll)p<<(x*3);
}
#define pii  pair<ll,int>
#define  mp  make_pair
int bfs(ll s)
{
    if(done(s)) return 1;
    queue< pii  > q;
    q.push(mp(s,0));
    vis.clear();
    vis[s]=1;
    while(!q.empty()) {
        pii tt=q.front(); q.pop();
        ll u=tt.first;
        int d=tt.second+1;
        for(int i=0;i<n;i++) {
            int p=(u&(7ll<<(i*3)))>>(i*3);
            for(int j=1;j<=p;j++) {
                ll v=u;
                cover(v,i,p-j);
                if(!check(v,i)) break;
                if(done(v)) return d+1;
                if(vis[v]) continue;
                vis[v]=1;
                q.push(mp(v,d));
            }
            for(int j=1;p+j+B[i].l<=6;j++) {
                ll v=u;
                cover(v,i,p+j);
                if(!check(v,i)) break;
                if(done(v)) return d+1;
                if(vis[v]) continue;
                vis[v]=1;
                q.push(mp(v,d));
            }
        }
    }
    return -1;
}

int main()
{
    while(cin>>n&&n)
    {
       ll s=0;
     //  cout<<s<<endl;
        for(int i=0;i<n;i++)
        {
            int t,lx,ly,rx,ry;
            cin>>t>>lx>>ly>>rx>>ry;
            if(lx==rx) {
                B[i].t=0;
                B[i].l=ry-ly+1;
                B[i].c=lx;
                s|=((ll)ly<<(3*i));
            }
            else {
                B[i].t=1;
                B[i].l=rx-lx+1;
                B[i].c=ly;
                s|=((ll)lx<<(3*i));
            }
          //  cout<<"done:"<<done(s)<<endl;
        }
        cin>>r;
       // print(s);
        cout<<bfs(s)<<endl;
    }
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/oilover/article/details/20697463


,
  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  2. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。