大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。
题目：给出一个二维图，以及一个起点，m个中间点，求出从起点出发，到达每一个中间的最小步数。
思路：由于图的大小最大是100*100，所以要使用bfs求出当中每两个点之间的最小距离。然后依据这些步数，建立一个新的图，使用dfs求出最佳步数。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define INF 100000000
using namespace std;
char ma[103][103];
int vis[103][103];
int map[6][6],net[6];
int m,n,k;
struct node
{
int x,y;
int k;
}t;
queue<node>q;
int bfs(int x,int y,int l,int r)
{
memset(vis,0,sizeof(vis));
while(!q.empty())
{
q.pop();
}
vis[x][y]=1;
t.x=x,t.y=y,t.k=0;
q.push(t);
while(!q.empty())
{
t=q.front();
q.pop();
x=t.x;y=t.y;
if(x==l&&y==r)
{
return t.k;
}
t.k++;
if(x>=2&&ma[x-1][y]!='#'&&!vis[x-1][y])
{
t.x=x-1;t.y=y;
vis[t.x][t.y]=1;
q.push(t);
}
if(y>=2&&ma[x][y-1]!='#'&&!vis[x][y-1])
{
t.x=x;t.y=y-1;
vis[t.x][t.y]=1;
q.push(t);
}
if(x+1<=m&&ma[x+1][y]!='#'&&!vis[x+1][y])
{
t.x=x+1;t.y=y;
vis[t.x][t.y]=1;
q.push(t);
}
if(y+1<=n&&ma[x][y+1]!='#'&&!vis[x][y+1])
{
t.x=x;t.y=y+1;
vis[t.x][t.y]=1;
q.push(t);
}
}
return INF;
}
int ans=INF;
void dfs(int x,int step,int sum)
{
if(step==k)
{
if(ans>sum) ans=sum;
return;
}
for(int i=0;i<=k;i++)
if(!net[i])
{
net[i]=1;
dfs(i,step+1,sum+map[x][i]);
net[i]=0;
}
}
int main()
{
int d[6][2];
while(cin>>m>>n,m,n)
{
int x=0,y=0,l,r,sum;
ans=INF;
for(int i=1;i<=m;i++)
{
scanf("%s",&ma[i][1]);
if(!x)
for(int j=1;j<=n;j++)
if(ma[i][j]=='@')
{
x=i,y=j;
break;
}
}
d[0][0]=x;d[0][1]=y;
cin>>k;
for(int i=1;i<=k;i++)
{
cin>>d[i][0]>>d[i][1];
}
for(int i=0;i<k;i++)
{
x=d[i][0],y=d[i][1];
for(int j=i+1;j<=k;j++)
{
l=d[j][0],r=d[j][1];
sum=bfs(x,y,l,r);
if(sum<INF) map[i][j]=map[j][i]=sum;
else map[i][j]=map[j][i]=INF;
//cout<<sum<<endl;
}
}
net[0]=1;
dfs(0,0,0);
if(ans<INF) cout<<ans<<endl;
else cout<<-1<<endl;
}
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/117918.html原文链接：https://javaforall.net
