杭州现场赛的题。BFS+DFS
#include <iostream>
#include<cstdio>
#include<cstring>
#define inf 9999999
using namespace std; char mp[105][105];
int sq[5][5];
int step[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
struct pos
{
int x,y;
}; int n,m,prn,x,y,tmp,ans,cnt;
bool viss[5];
int bfs(pos bg,pos ed)
{
int i;
pos que[20000];
int front=0,rear=1;
bool vis[105][105]={false};
vis[bg.x][bg.y]=true;
que[0]=bg;
int cnt[20000]={0};
if(ed.x==bg.x&&ed.y==bg.y)
return 0;
while(rear>front)
{
for(i=0;i<4;i++)
{
if(que[front].x+step[i][0]>=0&&que[front].x+step[i][0]<n&&que[front].y+step[i][1]>=0&&que[front].y+step[i][1]<m&&
mp[que[front].x+step[i][0]][que[front].y+step[i][1]]!='#'&&!vis[que[front].x+step[i][0]][que[front].y+step[i][1]])
{
que[rear].x=que[front].x+step[i][0];
que[rear].y=que[front].y+step[i][1];
vis[que[rear].x][que[rear].y]=true;
cnt[rear]=cnt[front]+1;
if(que[rear].x==ed.x&&que[rear].y==ed.y)
return cnt[rear];
// cout<<que[rear].x<<' '<<que[rear].y<<endl;
rear++;
}
}
front++;
}
return -1;
}
void cal(int q)
{
int i;
if(cnt==prn)
return;
viss[q]=true;
for(i=1;i<=prn;i++)
{
if(!viss[i])
{
tmp+=sq[q][i];
viss[i]=true;
cnt++;
cal(i);
if(cnt==prn)
if(tmp<ans)
ans=tmp;
cnt--;
tmp-=sq[q][i];
viss[i]=false;
}
}
viss[q]=false;
return;
}
int main()
{
// freopen("in.txt","r",stdin);
while(cin>>n>>m&&(n+m))
{
memset(sq,0,sizeof(sq));
memset(viss,false,sizeof(viss));
int i,j;
ans=inf;
tmp=0;
cnt=0;
pos st;
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
cin>>mp[i][j];
if(mp[i][j]=='@')
{
st.x=i;
st.y=j;
}
}
}
cin>>prn;
pos pr[4];
for(i=0;i<prn;i++)
{
cin>>pr[i].x>>pr[i].y;
pr[i].x--;
pr[i].y--;
// cout<<pr[i].x<<" "<<pr[i].y<<endl;
}
bool f=true;
for(i=0;i<prn;i++)
{
sq[0][i+1]=bfs(st,pr[i]);
if(sq[0][i+1]==-1)
{
f=false;
break;
}
}
if(!f)
{
cout<<-1<<endl;
continue;
}
for(i=0;i<prn;i++)
{
for(j=0;j<prn;j++)
{
if(i==j)
continue;
int t=bfs(pr[i],pr[j]);
sq[i+1][j+1]=sq[j+1][i+1]=t;
}
}
cal(0);
cout<<ans<<endl;
}
return 0;
}