Description

有一个N*N的迷宫，其中有一些宝藏，现在，小A要从入口(1,1)出发，到达出口（N，N），每次，小A只能从当前的格子走到上下左右四个格子，为了不空手而归，小A决定要拿到所以的宝藏。请问，他最少要走多少步，才能拿到宝藏？

Input Format

第一行：一个整数N，表示迷宫的大小。

第二到第（N+1）行，每行有N个字符，代表迷宫的情况，其中‘0’代表路径，‘1’代表墙面，‘2’代表宝藏

Output Format

一行，一个整数，表示最少步数，或者输出No Solution，表示无法取到所以宝藏

Sample Input

3

011

020

110

Sample Output

4

Hint

100%，N<=30,宝藏个数<=13

Solution

首先，宝藏个数<=13，自然想到状压DP， 用二进制数表示状态，‘1’代表这个宝藏去过了，‘0’代表没有，

那么可以用F[i][S]表示状态为S时，且位于第i个宝藏的最短步数。

那么容易得到方程F[i][S]=min{F[k][S^(1<<(i-1))]+dis[i][k]},其中1<=k<=宝藏个数，dis[i][k]表示第i个宝藏到第k个宝藏的最少步数

那么最后答案就为min{F[i][(1<<m)-1]+toEnd[i]},其中toEnd[i]表示从宝藏i到点（N ,N )的最少步数.

dis数组和toEnd数组可以用bfs预处理得到，细节也不少，当无法到达终点或有至少一个宝藏拿不到就是无解的情况，而且要特判没有宝藏时直接输出到终点的距离

当初挂了好几次，主要有以下几点原因：

1. 记忆化时tmp忘记初始化为INF，导致答案都为-1
2. 没有考虑没有宝藏的情况（m==0)
3. 没有考虑到不了终点的情况
4. 方程原来写成转移到DP(i, S ^ (1 << (i - 1))，应该是'(p-1)'
5. 读入时临时字符串数组开小，导致RE

Code

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int dx[4] = {0, 0, 1, -1};const int dy[4] = {1, -1, 0, 0};struct point {    point(int a, int b) {x = a, y = b;}    int x, y;};struct info {    int x, y;} bag[32];int n, a[32][32], m, f[32][1 << 16], dis[32][32], toEnd[32], toBag[32];int d[32][32];bool vis[32][32];queue
        
          q;bool flag;void bfs(int k, int sx, int sy) {    memset(vis, 0, sizeof(vis));    memset(d, -1, sizeof(d));    d[sx][sy] = 0;    while (!q.empty()) q.pop();    q.push(point(sx, sy));    vis[sx][sy] = 1;    while (!q.empty()) {        point u = q.front();        int x = u.x, y = u.y;        q.pop();        for (int i = 0; i < 4; ++i) {            int nx = x + dx[i], ny = y + dy[i];            if (nx <= 0 || ny <= 0 || nx > n || ny > n || vis[nx][ny] || a[nx][ny]) continue;            vis[nx][ny] = 1;            d[nx][ny] = d[x][y] + 1;            q.push(point(nx, ny));        }    }    for (int i = k + 1; i <= m; ++i) {        int x = bag[i].x, y = bag[i].y;        if (d[x][y] == -1) {            if (k == 0) flag = 1;            continue;        }        if (k == 0) toBag[i] = d[x][y];        else dis[k][i] = dis[i][k] = d[x][y];    }    if (d[n][n] == -1) flag = 1;    toEnd[k] = d[n][n];}int DP(int p, int S) {    int &tmp = f[p][S];    if (tmp != -1) return tmp;    tmp = (int)1e9;    for (int i = 1; i <= m; ++i) {        if (i == p) continue;        if (!((1 << (i - 1))&S)) continue;        tmp = min(tmp, DP(i, S ^ (1 << (p - 1))) + dis[i][p]);    }    return tmp;}int main() {    scanf("%d", &n);    memset(dis, 0x3f, sizeof(dis));    for (int i = 1; i <= n; ++i) {        char s[32];        scanf("%s\n", s);        for (int j = 0; j < n; ++j) {            a[i][j + 1] = s[j] - '0';            if (a[i][j + 1] == 2) {                a[i][j + 1] = 0;                bag[++m].x = i;                bag[m].y = j + 1;            }        }    }    bfs(0, 1, 1);    if (flag) {        printf("No Solution\n");        return 0;    }    for (int i = 1; i <= m; ++i)        bfs(i, bag[i].x, bag[i].y);    int Ans = (int)1e9;    memset(f, -1, sizeof(f));    for (int i = 1; i <= m; ++i)        f[i][1 << (i - 1)] = toBag[i];    for (int i = 1; i <= m; ++i)        Ans = min(Ans, DP(i, (1 << m) - 1) + toEnd[i]);    if (m == 0) Ans = toEnd[0];    printf("%d\n", Ans);    return 0;}
        
       
      
     
    

---