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

思路：先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<