有没有状态压缩BFS过了的大神能分享一下代码或者说一下剪枝。

using namespace std;

const int MAXN = 30;
const int MOD7 = 1000000007ll;
const int MOD9 = 1000000009ll;
const int INF = 2000000000;
const double ESP = 1e-9;
const double PI = 3.14159265358979;
const int dir_4r[] = { -1, 1, 0, 0 };
const int dir_4c[] = { 0, 0, -1, 1 };
const int dir_8r[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
const int dir_8c[] = { -1, 0, 1, -1, 1, -1, 0, 1 };

struct Step
{
	int r;
	int c;
	int s;//清理状态
	int t;
	Step() {}
	Step(int rr, int cc, int ss, int tt) :r(rr), c(cc), s(ss), t(tt) {}
};

int ans;
int w, h, cnt;
int mat[MAXN][MAXN];//0干净 1肮脏 2家具
int mint[MAXN][MAXN][1 << 12];
int visited[MAXN][MAXN][1 << 12];
queue<Step> que;
map<pair<int, int>, int> hashT;

void bfs()
{
	while (!que.empty())
	{
		Step cur = que.front();
		que.pop();
		if (cur.t >= ans)
			continue;
		if (mint[cur.r][cur.c][cur.s] != -1 && cur.t > mint[cur.r][cur.c][cur.s])
			continue;
		mint[cur.r][cur.c][cur.s] = cur.t;
		if (cur.s == ((1 << cnt) - 1))
		{
			ans = cur.t;
			return;
		}
		for (int i = 0; i < 4; ++i)
		{
			int nr = cur.r + dir_4r[i];
			int nc = cur.c + dir_4c[i];
			if (nr >= 0 && nr < h && nc >= 0 && nc < w)
			{
				if (mat[nr][nc] == 0 && !visited[nr][nc][cur.s])
				{
					que.push(Step(nr, nc, cur.s, cur.t + 1));
					visited[nr][nc][cur.s] = true;
				}
				else if (mat[nr][nc] == 1)
				{
					int ns = cur.s | (1 << (hashT[make_pair(nr, nc)]));
					if (!visited[nr][nc][ns])
					{
						que.push(Step(nr, nc, ns, cur.t + 1));
						visited[nr][nc][ns] = true;
					}
				}
			}
		}
	}
}

int main()
{
	char s[MAXN];
	while (cin >> w >> h)
	{
		if (w == 0)
			break;
		cnt = 0;
		ans = INF;
		hashT.clear();
		memset(mint, -1, sizeof(mint));
		memset(visited, 0, sizeof(visited));
		while (!que.empty())
			que.pop();

		for (int i = 0; i < h; ++i)
		{
			scanf("%s", s);
			for (int j = 0; j < w; ++j)
			{
				if (s[j] == '.')
					mat[i][j] = 0;
				else if (s[j] == '*')
				{
					mat[i][j] = 1;
					hashT[make_pair(i, j)] = cnt++;
				}
				else if (s[j] == 'x')
					mat[i][j] = 2;
				else
				{
					mat[i][j] = 0;
					que.push(Step(i, j, 0, 0));
					mint[i][j][0] = 0;
					visited[i][j][0] = true;
				}
			}
		}
		bfs();
		if (ans == INF)
			printf("-1\n");
		else
			printf("%d\n", ans);
	}

	//system("pause");
	return 0;
}