1 #include <cstdio>  2 #include <queue>  3 #include <cstring>  4 #include <algorithm>  5 #define maxn 1000  6 using namespace std;  7 const int inf=1<<29;  8   9 int n,m; 10 char g[16][16]; 11 int gg[16][16]; 12 struct node 13 { 14     int x1,y1,x2,y2; 15 } p[maxn],st3; 16 int dis[16][16]; 17 int dir[4][2]= {{0,1},{0,-1},{1,0},{-1,0}}; 18 int dp[1<<16][16]; 19 bool vis[maxn][maxn]; 20  21 int bfs(int s,int t) 22 { 23     queue<node>q; 24     memset(vis,false,sizeof(vis)); 25     for(int i=0; i<n; i++) 26     { 27         for(int j=0; j<n; j++) 28         { 29             dis[i][j]=inf; 30         } 31     } 32     node st; 33     st.x1=p[s].x2; 34     st.y1=p[s].y2; 35     dis[p[s].x2][p[s].y2]=0; 36     vis[p[s].x2][p[s].y2]=true; 37     q.push(st); 38     while(!q.empty()) 39     { 40         node st1=q.front(); 41         q.pop(); 42         if(st1.x1==p[t].x1&&st1.y1==p[t].y1) 43         { 44             return dis[p[t].x1][p[t].y1]; 45         } 46         for(int i=0; i<4; i++) 47         { 48             int xx=st1.x1+dir[i][0]; 49             int yy=st1.y1+dir[i][1]; 50             if(xx>=0&&xx<n&&yy>=0&&yy<n&&g[xx][yy]!=‘#‘) 51             { 52                 if(!vis[xx][yy]) 53                 { 54                     dis[xx][yy]=dis[st1.x1][st1.y1]+1; 55                     st3.x1=xx; 56                     st3.y1=yy; 57                     vis[xx][yy]=true; 58                     q.push(st3); 59                 } 60             } 61         } 62     } 63     return -1; 64 } 65  66 int main() 67 { 68     while(scanf("%d%d",&n,&m)!=EOF) 69     { 70         memset(g,0,sizeof(g)); 71         for(int i=0; i<n; i++) 72         { 73             scanf("%s",g[i]); 74         } 75         for(int i=0; i<m; i++) 76         { 77             scanf("%d%d%d%d",&p[i].x1,&p[i].y1,&p[i].x2,&p[i].y2); 78             p[i].x1-=1; 79             p[i].y1-=1; 80             p[i].x2-=1; 81             p[i].y2-=1; 82         } 83         memset(dp,-1,sizeof(dp)); 84         for(int i=0; i<m; i++) 85         { 86             for(int j=0; j<m; j++) 87             { 88                 if(i==j) gg[i][j]=0; 89                 else 90                 gg[i][j]=bfs(i,j); 91             } 92         } 93         for(int i=0; i<m; i++) 94         { 95             dp[1<<i][i]=0; 96         } 97         for(int i=0; i<(1<<m); i++) 98         { 99             for(int j=0; j<m; j++)100             {101                 if((i&(1<<j))==0) continue;102                 if(dp[i][j]==-1)  continue;103                 for(int k=0; k<m; k++)104                 {105                     if(gg[j][k]==-1) continue;106                     if(i&(1<<k)) continue;107                     if(dp[i|(1<<k)][k]==-1) dp[i|(1<<k)][k]=dp[i][j]+gg[j][k];108                     else dp[i|(1<<k)][k]=min(dp[i|(1<<k)][k],dp[i][j]+gg[j][k]);109                 }110             }111         }112         int ans=inf;113         for(int i=0; i<m; i++)114         {115             if(dp[(1<<m)-1][i]!=-1)116             ans=min(ans,dp[(1<<m)-1][i]);117         }118         if(ans==inf) printf("-1\n");119         else120         printf("%d\n",ans);121     }122     return 0;123 }