题目大意:地图上有些管道，在管道行走里不需要花费时间，但从一个管道的出口走到另一个管道的入口则需要花费时间，问走完所有管道最短的时间，如果不行，则输出-1.
先用bfs处理出每两个点之间的距离，这样就可以知道每个管道出口到其他出口的距离，然后就是怎么走这些管道，如果直接深搜有15！种情况，肯定不行，而n,m最大都才15，总状态一共就215-1个，这样我们枚举每个状态，然后再枚举这个状态已经走过的管道，最后枚举这个状态没走到的管道，dp[i][j]就代表i状态最后走的是j管道的最短时间。
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int inf=0x3f3f3f3f;
const int ne[][]={{,},{,},{,-},{-,}};
struct Node{
int x,y,t;
Node(){}
Node(int x,int y,int t):x(x),y(y),t(t){}
};
int n,m,sn,ans,dis[][][][],vis[][];
int x1[],y1[],x2[],y2[],dp[<<][],cf2[]={};
char s[][];
void bfs(int x,int y)
{
memset(vis,,sizeof(vis));
vis[x][y]=;
queue<Node> q;
q.push(Node(x,y,));
while(!q.empty())
{
Node p=q.front();
q.pop();
dis[x][y][p.x][p.y]=p.t;
for(int i=;i<;i++)
{
int dx=p.x+ne[i][];
int dy=p.y+ne[i][];
if(dx<=||dx>n||dy<=||dy>n)
continue;
if(!vis[dx][dy]&&s[dx][dy]!='#')
{
vis[dx][dy]=;
q.push(Node(dx,dy,p.t+));
}
}
}
}
int main()
{
for(int i=;i<=;i++)
cf2[i]=cf2[i-]<<;
while(~scanf("%d%d",&n,&m))
{
memset(dp,inf,sizeof(dp));
memset(dis,inf,sizeof(dis));
for(int i=;i<=n;i++)
scanf("%s",s[i]+);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
bfs(i,j);//预处理出距离
for(int i=;i<m;i++)
scanf("%d%d%d%d",&x1[i],&y1[i],&x2[i],&y2[i]);
for(int i=;i<m;i++)
dp[<<i][i]=;//第一个走的管道不需要花费时间
int maxm=(<<m)-;
for(int i=;i<maxm;i++)
{
for(int j=;j<m;j++)
{
if(i&cf2[j])//枚举已经走了的
{
for(int k=;k<m;k++)
if(!(i&cf2[k]))//枚举还没走的
dp[i+cf2[k]][k]=min(dp[i+cf2[k]][k],dp[i][j]+dis[x2[j]][y2[j]][x1[k]][y1[k]]);
}
}
}
int ans=inf;
for(int i=;i<m;i++)
ans=min(ans,dp[maxm][i]);
if(ans>=inf)
printf("%d\n",-);
else
printf("%d\n",ans);
}
return ;
}
马里奥