题意：求经过所有的管道的最短路程，管道内的时间不算

思路：首先BFS处理出管道出口到其他管道入口的距离，然后在队友的指导下明白了状态转移

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; const int MAXN = 16; const int INF = 0x3f3f3f3f; struct Node { int sx, sy, ex, ey; } node[MAXN]; struct point { int x, y, step; }; char g[MAXN][MAXN]; int n, m, dp[1<
       
         q; point a; a.x = sx, a.y = sy, a.step = 0; q.push(a); vis[sx][sy] = 1; while (!q.empty()) { point cur = q.front(); q.pop(); if (cur.x == ex && cur.y == ey) { dis[from][to] = cur.step; return; } for (int i = 0; i < 4; i++) { int nx = cur.x + dx[i]; int ny = cur.y + dy[i]; if (g[nx][ny] == '#' || vis[nx][ny]) continue; if (nx > 0 && nx <= n && ny > 0 && ny <= n) { vis[nx][ny] = 1; point b; b.x = nx, b.y = ny; b.step = cur.step + 1; q.push(b); } } } } int main() { while (scanf("%d%d", &n, &m) != EOF) { for (int i = 1; i <= n; i++) scanf("%s", g[i]+1); for (int i = 0; i < m; i++) scanf("%d%d%d%d", &node[i].sx, &node[i].sy, &node[i].ex, &node[i].ey); memset(dis, -1, sizeof(dis)); for (int i = 0; i < m; i++) for (int j = 0; j < m; j++) bfs(i, j, node[i].ex, node[i].ey, node[j].sx, node[j].sy); memset(dp, -1, sizeof(dp)); for (int i = 0; i < m; i++) dp[1<
        
          dp[all-1][i]) ans = dp[all-1][i]; } printf("%d\n", ans); } return 0; }