这道题写的惨不忍睹，首先我没有用struct用pair一直MLE，然后初始化少考虑了BFS拓展不到的点，一直WA
#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<stdlib.h>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include <ctype.h>
using namespace std;
//hdu 4856
const int MAXN=16;//之前写成15就没有过
int N;
int M;
const int INF=0x3f3f3f3f;
pair<int,int> st[MAXN];
pair<int,int> ed[MAXN];
int dis[MAXN][MAXN];
int mp[MAXN][MAXN];
int dx[]={0,-1,0,1};
int dy[]={-1,0,1,0};
int d[1<<MAXN][16];//status,output
int dp[40][MAXN];
void input()
{
char ch;
for(int i=1;i<=N;i++)
{
for(int j=1;j<=N;j++)
{
cin>>ch;
if(ch=='.') mp[i][j]=1;
else mp[i][j]=0;
}
}
for(int i=0;i<M;i++)
{
scanf("%d %d %d %d",&st[i].first,&st[i].second,&ed[i].first,&ed[i].second);
}
}
struct Node
{
int x;
int y;
int step;
Node(){}
Node(int sx,int sy,int s)
{
x=sx;
y=sy;
step=s;
}
};
queue<pair<int,int> > q;
int bfs2(int idx,int g)//只计算tunnel涉及的点
{
int dst[20][20]; //length from ed[idx] to [i,j]
bool used[20][20];
memset(used,true,sizeof(used));
memset(dst,-1,sizeof(dst));
dst[ed[idx].first][ed[idx].second]=0;
while(!q.empty()) q.pop();
q.push(ed[idx]);
pair<int,int>tmp;
while(!q.empty())
{
tmp=q.front();
int x=tmp.first;
int y=tmp.second;
if(x==st[g].first&&y==st[g].second)
{
return dst[x][y];
}
q.pop();
used[x][y]=false;
for(int i=0;i<4;i++)
{
if(x+dx[i]>0&&x+dx[i]<=N&&y+dy[i]>0&&y+dy[i]<=N)
{
if(mp[x+dx[i]][y+dy[i]]==1&&used[x+dx[i]][y+dy[i]]==1)
{
dst[x+dx[i]][y+dy[i]]=dst[tmp.first][tmp.second]+1;
q.push(make_pair(x+dx[i],y+dy[i]));
}
}
}
}
return -1;
}
void bfs(int idx)
{
queue<Node>q;
int dst[20][20]; //length from ed[idx] to [i,j]
bool used[20][20];
memset(used,true,sizeof(used));
memset(dst,0x3f,sizeof(dst));
dst[ed[idx].first][ed[idx].second]=0;
q.push(Node(ed[idx].first,ed[idx].second,0));
Node tmp;
while(!q.empty())
{
tmp=q.front();
q.pop();
int x=tmp.x;
int y=tmp.y;
used[x][y]=false;
for(int i=0;i<4;i++)
{
if(x+dx[i]>0&&x+dx[i]<=N&&y+dy[i]>0&&y+dy[i]<=N)
{
if(mp[x+dx[i]][y+dy[i]]==1&&used[x+dx[i]][y+dy[i]]==1)
{
used[x+dx[i]][y+dy[i]]=false;
dst[x+dx[i]][y+dy[i]]=tmp.step+1;
q.push(Node(x+dx[i],y+dy[i],tmp.step+1));
}
}
}
}
for(int i=0;i<M;i++)
{
if(idx!=i)//&&used[st[i].first][st[i].second]==0
dis[idx][i]=dst[st[i].first][st[i].second];
else
dis[idx][i]=0;//如果是 if(idx!=i&&used[st[i].first][st[i].second]==0),则dis[idx][i]=0会WA，=0只考虑了dis[i][i]=0,但实际上，BFS无法扩展到的点距离也要设为INF，且INF对DP无影响
}
}
//void bfs(int idx) //不用struct会MLE
//{
// int dst[20][20]; //length from ed[idx] to [i,j]
// bool used[20][20];
// memset(used,true,sizeof(used));
// memset(dst,0x3f,sizeof(dst));
// dst[ed[idx].first][ed[idx].second]=0;
// while(!q.empty()) q.pop();
// q.push(ed[idx]);
// pair<int,int>tmp;
// while(!q.empty())
// {
// tmp=q.front();
// q.pop();
// int x=tmp.first;
// int y=tmp.second;
// used[x][y]=false;
// //if(idx==0)
// // cout<<x<<" "<<y<<endl;
// for(int i=0;i<4;i++)
// {
// if(x+dx[i]>0&&x+dx[i]<=N&&y+dy[i]>0&&y+dy[i]<=N)
// {
// if(mp[x+dx[i]][y+dy[i]]==1&&used[x+dx[i]][y+dy[i]]==1)
// {
// used[x+dx[i]][y+dy[i]]==0;
// dst[x+dx[i]][y+dy[i]]=dst[tmp.first][tmp.second]+1;
// q.push(make_pair(x+dx[i],y+dy[i]));
// }
// }
// }
// }
// for(int i=0;i<M;i++)
// {
// dis[idx][i]=dst[st[i].first][st[i].second];
// // cout<< dis[idx][i]<<endl;
// }
// // cout<<endl;
// dis[idx][idx]=0;
//}
void run()
{
// for(int i=0;i<M;i++) //这样可以省内存
// {
// for(int j=0;j<M;j++)
// {
// if(i==j) dis[i][j]=0;
// else
// {
// dis[i][j]=bfs2(i,j);
// }
//
// }
// }
for(int i=0;i<M;i++)
{
bfs(i);
}
for(int i=0;i<(1<<M);i++)
{
for(int j=0;j<M;j++)
{
d[i][j]=INF;
}
}
for(int i=0;i<M;i++)
{
//d[0][i]=0;
d[1<<i][i]=0;
//cout<<hex<<(1<<i)<<endl;
}
for(int x=0;x<(1<<M);x++)
{
for(int i=0;i<M;i++)
{
if(x&(1<<i)) continue;
for(int k=0;k<M;k++)
{
d[x|1<<i][i]=min(d[x|1<<i][i],d[x][k]+dis[k][i]);
}
}
}
int ans=INF;
for(int i=0;i<M;i++)
{
ans=min(ans,d[(1<<M)-1][i]);
}
if(ans==INF)
{
printf("-1\n");
}
else
{
printf("%d\n",ans);
}
}
int main()
{
freopen("input.txt","r",stdin);
// freopen("data.txt","r",stdin);
// freopen("out1.txt","w",stdout);
while(scanf("%d %d",&N,&M)!=EOF)
{
input();
run();
}
return 0;
}