计蒜客 藏宝图 （bfs + 状压）

传送门

思路：

典型的bfs + 状压啊，一个入口出口，还要拿到地图中多个东西，而且同一个点重复走的话不好标记，这时候就标记状态啊/。。

md，退役垃圾狗。。。

答案 ：48

PS：

    这里走回出口没必要在跑一遍bfs，只需要走到出口时判断一下是否所有箱子都拿到了即可。

#include <bits/stdc++.h>

using namespace std;
int a[15][11] = {
	{0,0,0,0,0,0,0,0,0,0,0},
	{0,1,0,0,0,0,0,0,2,0,0},
	{0,0,0,0,-1,0,0,2,0,0,0},
	{0,0,-1,0,0,2,0,0,-1,0,0},
	{0,0,2,0,0,0,-1,0,0,2,0},
	{0,0,-1,0,0,2,0,-1,0,0,0},
	{0,0,0,-1,0,0,0,0,-1,0,0},
	{0,0,0,0,0,0,-1,0,0,2,0},
	{0,0,-1,0,-1,0,0,2,0,0,0},
	{0,0,2,0,0,0,0,-1,-1,0,0},
	{0,0,0,-1,0,0,-1,2,0,0,0}
};
int go[4][2] = {0,1,1,0,0,-1,-1,0};
struct node
{
	int x,y,sta,step;
	node(int xx = 0,int yy = 0,int state = 0,int s = 0)
	{
		x = xx,y = yy,sta = state,step = s;
	}

};
bool vis[20][20][1050];
int num[20][20];
int get_sta(int x,int y,int cur)
{
	int p[20];
	for(int i = 0;i < 10;++i)
	{
		p[i] = (cur >> i) & 1;
	}
	p[num[x][y]] = 1;
	int now = 0;
	for(int i = 9;i >= 0;--i)
		now = now * 2 + p[i];
	return now;
}

int bfs(int st,int dt)
{
	memset(vis,0,sizeof vis);
	queue<node>Q;
	while(!Q.empty()) Q.pop();
	Q.push(node(st,dt,0,0));
	vis[st][dt][0] = 1;
	while(!Q.empty())
	{
		node q = Q.front();Q.pop();
		if(q.x == 1 && q.y == 1 && q.sta == 1023)
			return q.step;
		for(int i = 0;i < 4;++i)
		{
			int tx = q.x + go[i][0];
			int ty = q.y + go[i][1];
			int sta = q.sta;
			if(a[tx][ty] == 2)
			{
				sta = get_sta(tx,ty,sta);
			}
			if(tx < 1 || ty < 1|| tx > 10 || ty > 10 || a[tx][ty] == -1 || vis[tx][ty][sta])
				continue;
			vis[tx][ty][sta] = 1;
			Q.push(node(tx,ty,sta,q.step + 1));
		}
	}
	return -1;
}
int main()
{
	memset(num,-1,sizeof num);
	int cnt = 0;
	for(int i = 1;i <= 10;++i)
	{
		for(int j = 1;j <= 10;++j)
		{
			if(a[i][j] == 2)
			{
				//printf("%d %dn",i,j);
				num[i][j] = cnt++;
			}
		}
	}
	//cout << cnt << endl;
	cout << bfs(1,1) << endl;
	return 0;
}

最后

以上就是孤独唇彩为你收集整理的计蒜客 藏宝图 （bfs + 状压）的全部内容，希望文章能够帮你解决计蒜客 藏宝图 （bfs + 状压）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。