题目大意:地图上有些管道，在管道行走里不需要花费时间，但从一个管道的出口走到另一个管道的入口则需要花费时间，问走完所有管道最短的时间，如果不行，则输出-1.

　　先用bfs处理出每两个点之间的距离，这样就可以知道每个管道出口到其他出口的距离，然后就是怎么走这些管道，如果直接深搜有15！种情况，肯定不行，而n,m最大都才15，总状态一共就2¹⁵-1个，这样我们枚举每个状态，然后再枚举这个状态已经走过的管道，最后枚举这个状态没走到的管道，dp[i][j]就代表i状态最后走的是j管道的最短时间。　

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 const int inf=0x3f3f3f3f; 6 const int ne[4][2]={
    {
    0,1},{
    1,0},{
    0,-1},{-1,0}}; 7 struct Node{ 8     int x,y,t; 9     Node(){}10     Node(int x,int y,int t):x(x),y(y),t(t){}11 };12 int n,m,sn,ans,dis[20][20][20][20],vis[20][20];13 int x1[20],y1[20],x2[20],y2[20],dp[1<<18][20],cf2[18]={
    1};14 char s[20][20];15 void bfs(int x,int y)16 {17     memset(vis,0,sizeof(vis));18     vis[x][y]=1;19     queue
         
           q;20     q.push(Node(x,y,0));21     while(!q.empty())22     {23         Node p=q.front();24         q.pop();25         dis[x][y][p.x][p.y]=p.t;26         for(int i=0;i<4;i++)27         {28             int dx=p.x+ne[i][0];29             int dy=p.y+ne[i][1];30             if(dx<=0||dx>n||dy<=0||dy>n)31                 continue;32             if(!vis[dx][dy]&&s[dx][dy]!='#')33             {34                 vis[dx][dy]=1;35                 q.push(Node(dx,dy,p.t+1));36             }37         }38     }39 }40 int main()41 {42     for(int i=1;i<=15;i++)43         cf2[i]=cf2[i-1]<<1;44     while(~scanf("%d%d",&n,&m))45     {46         memset(dp,inf,sizeof(dp));47         memset(dis,inf,sizeof(dis));48         for(int i=1;i<=n;i++)49             scanf("%s",s[i]+1);50         for(int i=1;i<=n;i++)51             for(int j=1;j<=n;j++)52                 bfs(i,j);//预处理出距离        53         for(int i=0;i
          
           =inf)74             printf("%d\n",-1);75         else76             printf("%d\n",ans);77     }78     return 0;79 }