点这里 打开题目链接 点击打开链接
题目就是我们玩过的推箱子；
一顿暴力广搜；加状态标记。状态压缩需要用到一个类似于康拓的思想来压缩；所以容易TLE，搜索就是用一个int型的数字来表示一个状态，
压缩的和代码
void set_C()
{
memset(C,,sizeof(C));
int i,j;
for(i=; i<=; i++)
{
C[i][]=;
for(j=; j<=; j++)
C[i][j]=C[i-][j-]+C[i-][j];// C数组是组合数，C n，m
}
} int binary_cantor(int num,int g)
{
int w,ans=,y=g;
for(int i=; i>=; i--)
{
if(num&(<<i))
{
ans+=C[i][g];
g--;
if(g==) break;
}
}
return ans;
}
值得注意判断死角是相邻的两个方向不能够移动。
剩下的在完整代码中说明。
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <bitset>
#include <vector>
#include <iostream>
#include <algorithm>
#include <stdlib.h> using namespace std;
typedef long long LL;
const int INF=2e9+1e8;
const int MOD=1e9+;
const int MM=;
const int VIS=*+;
const int LEN=+;
int n,m,dir[][]= {{,},{,},{-,},{,-}};// 最好是让dir数组顺时针或者逆时针 方向转动
string Push_Sokoban;// 记录地图中哪些地方有枪
int C[][];//组合数
int aim; // 用一个二进制位记录仓库的位置
bool vis[VIS]; //标记状态的数组
struct point
{
int x,y;
};
struct node
{
int pos,step,stauts;
};
void set_C()// 递推打印组合数；
{
memset(C,,sizeof(C));
int i,j;
for(i=; i<=; i++)
{
C[i][]=;
for(j=; j<=; j++)
C[i][j]=C[i-][j-]+C[i-][j];
}
} int binary_cantor(int num,int g)//压缩状态； 表示num这个数有g位二进制位为1 返回的数字表示num这个数在他们的排列中第几小
{
int w,ans=,y=g;
for(int i=; i>=; i--)
{
if(num&(<<i))
{
ans+=C[i][g];
g--;
if(g==) break;
}
}
return ans;
}
bool is_out(int x,int y)// 是否越界
{
if(x>=&&x<n&&y>=&&y<m) return true;
return false;
}
/***************************/
//一维 与 二维 坐标的相互转化
int change(int x,int y)
{
return x*m+y;
}
int change(point p)
{
return p.x*m+p.y;
}
point change(int x)
{
point p;
p.x=x/m,p.y=x%m;
return p;
}
/****************************/
bool is_arrive(int box,int pos,int num)// 判断该状态是否来过
{
int temp=binary_cantor(box,num);
int a=pos*LEN+temp;
if(!vis[a])
{
vis[a]=;// 未来过该状态则需要标记一下
return true;
}
return false;
}
bool check_dead(int box,int bpos)// 是否进入死角，死角意味着， 该箱子未到仓库，且无法移动
{
point p=change(bpos);
for(int i=; i<; i++)
{
if(!is_out(p.x+dir[i][],p.y+dir[i][])||Push_Sokoban[change(p.x+dir[i][],p.y+dir[i][])]=='*')
{
if(!is_out(p.x+dir[(i+)%][],p.y+dir[(i+)%][])||Push_Sokoban[change(p.x+dir[(i+)%][],p.y+dir[(i+)%][])]=='*')
if(!(aim&(<<bpos))) return false;
}
}
return true;
} // 下面就是广搜核心了
int bfs(int pos,int box,int number)// 全局变量注意清零
{
node first,second;
first.step=,first.pos=pos,first.stauts=box;
queue<node>q;
memset(vis,,sizeof(vis));
q.push(first);
while(!q.empty())
{
first=q.front();
// cout<<bitset < sizeof(int)*8 > (first.stauts)<<endl;
// cout<<"@ "<<first.pos<<endl;
if(aim==first.stauts) return first.step;
q.pop();
for(int i=; i<; i++)
{
point p=change(first.pos);
int x=p.x+dir[i][],y=p.y+dir[i][];
int bx=p.x+*dir[i][],by=p.y+*dir[i][];
int box_pos=change(bx,by);
box=first.stauts;
pos=change(x,y);
if(is_out(x,y)&&Push_Sokoban[pos]!='*')
{
if((box&(<<pos))&&is_out(bx,by)&&!(box&(<<box_pos))&&Push_Sokoban[box_pos]!='*')// 该位置上有箱子
{
box=box&(~(<<pos)),box=box|(<<box_pos);
if(is_arrive(box,pos,number)&&check_dead(box,box_pos)) //
{
// printf("ren pos =%d x=%d y=%d\n",pos,change(pos).x,change(pos).y);
second.pos=pos,second.stauts=box,second.step=first.step+;
q.push(second);
}
}
else if(!(box&(<<pos))&&is_arrive(box,pos,number))
{
// printf("ren pos =%d x=%d y=%d\n",pos,change(pos).x,change(pos).y);
second.pos=pos,second.stauts=box,second.step=first.step+;
q.push(second);
}
}
}
}
return -;
}
/************************** 本题难点就在与状态压缩，如何给定一个数，给定二进
制位1的个数，快速判断第几小，有点康拓的感觉
*******************************************/
int main(void)
{
int ncase;
set_C();
cin>>ncase;
while(ncase--)
{
scanf("%d%d",&n,&m);
Push_Sokoban.clear();
int man_pos;
int box=,num=;
aim=;
for(int i=; i<n; i++)
{
string s;
cin>>s;
for(int j=; j<m; j++)
{
if(s[j]=='m') man_pos=i*m+j,s[j]='.';
else if(s[j]=='b') s[j]='.',box=box|(<<(i*m+j)),num++;
else if(s[j]=='w') s[j]='.',aim=aim|(<<(i*m+j));
else if(s[j]=='+') s[j]='.',box=box|(<<(i*m+j)),aim=aim|(<<(i*m+j)),num++;
}
Push_Sokoban+=s;
}
//cout<<bitset < sizeof(int)*8 > (aim) <<endl;
printf("%d\n",bfs(man_pos,box,num));
}
return ;
}
康拓的题目，详见 点击打开链接