标准的TSP问题

m*n矩阵，有不超过10个需要走到的点，给出起点，问走最少的步子把所有点走完

BFS出每个必须走到的点的最短距离

然后状压DP即可

?

#include "stdio.h"
#include "string.h"
#include "queue"
using namespace std;

const int dir[4][2]={ {1,0},{-1,0},{0,1},{0,-1} };
int inf=0x7fffffff;
int aim,cnt,n,m,s_x,s_y;
int b[20];
int used[25][25];
int dp[5010][25];
char str[25][25];
int dis[25][25];
struct node
{
    int x,y,step;
};

struct Point
{
    int x,y;
}point[25];

int Min(int a,int b)
{
    if (a
  
   q;
    node cur,next;
    int i;
    cur.x=point[w].x;
    cur.y=point[w].y;
    memset(used,-1,sizeof(used));
    used[cur.x][cur.y]=0;
    q.push(cur);
    while (!q.empty())
    {
        cur=q.front();
        q.pop();
        for (i=0;i<4;i++)
        {
            next.x=cur.x+dir[i][0];
            next.y=cur.y+dir[i][1];
            if (next.x<0 || next.x>=n || next.y<0 || next.y>=m) continue;
            if (str[next.x][next.y]=='x') continue;
            if (used[next.x][next.y]==-1)
            {
                used[next.x][next.y]=used[cur.x][cur.y]+1;
                q.push(next);
                if (str[next.x][next.y]>='a' && str[next.x][next.y]<'o')
                    dis[w][str[next.x][next.y]-'a'+1]=dis[str[next.x][next.y]-'a'+1][w]=used[next.x][next.y];
            }
        }
    }
}

int main()
{
    int i,j,ii,ans,k;
    b[0]=0;
    b[1]=1;
    for (i=2;i<=15;i++)
        b[i]=b[i-1]*2;

    while (scanf("%d%d",&m,&n)!=EOF)
    {
        if (n+m==0) break;
        for (i=0;i
   
    dp[i][j]+dis[j][k]) && dp[i][j]!=-1 && dis[j][k]!=-1) dp[i|b[k]][k]=dp[i][j]+dis[j][k]; } ans=inf; for (i=1;i<=cnt;i++) if (dp[aim][i]!=-1) ans=Min(ans,dp[aim][i]); if (ans==inf) printf("-1\n"); else printf("%d\n",ans); } return 0; } 
   
  

?