POJ - 2688 Cleaning Robot

題意：求回收所有垃圾的最短路

思路：先BFS處理兩個垃圾的距離，然後DFS記憶化搜索

dp[i][state]表示處理到第i個後狀態是state的最短路

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int MAXN = 30;
const int INF = 0x3f3f3f3f;

struct Point {
	int x,y;
}point[20];
struct node {
	int x,y,step,f;
	node(int _x, int _y, int _step, int _f) {
		x = _x, y = _y, step = _step, f = _f;
	}
	bool operator< (const node a)const {
		return f > a.f;
	}
};
char map[MAXN][MAXN];
int n,m;
int dx[4] = {1,-1,0,0};
int	dy[4] = {0,0,1,-1};
int dis[MAXN][MAXN], vis[MAXN][MAXN];
int dp[12][1<<12],sum;

int check(int x, int y) {
	if (x > 0 && x <= n && y > 0 && y <= m && map[x][y] != 'x')
		return 1;
	return 0;
}

int getdiff(const Point &a, const Point &b) {
	return abs(a.x-b.x) + abs(a.y-b.y);
}

int bfs(const Point &a, const Point &b) {
	priority_queue q;
	q.push(node(a.x, a.y, 0, getdiff(a, b)));
	memset(vis, 0, sizeof(vis));
	vis[a.x][a.y] = 1;
	while (!q.empty()) {
		node cur = q.top();
		q.pop();
		if (cur.x == b.x && cur.y == b.y)
			return cur.step;
		for (int i = 0; i < 4; i++) {
			Point tmp;
			tmp.x = cur.x + dx[i];
			tmp.y = cur.y + dy[i];
			if (check(tmp.x, tmp.y) && !vis[tmp.x][tmp.y]) {
				vis[tmp.x][tmp.y] = 1;
				int f = cur.step+1+getdiff(tmp, b);
				q.push(node(tmp.x, tmp.y, cur.step+1, f));
			}
		}
	}
	return -1;
}

int getFlag(int i) {
	return 1<