训练赛-Move Between Numbers

题意:给你n个数,每个数有20个数字,每两个数字之间如果相等的数字数量为17个(一定是17),就能从一个数字到达另一个数字,给你两个数字编号,求从第一个数字编号到第二个数字编号之间最少需要走几次;

解题思路:建个图,然后最短路模板;

代码

#include<iostream>
#include<algorithm>
#include<cstring>
const int inf=0x3f3f3f;
using namespace std;
int a[][];
int dist[];
int visit[];
int main()
{
int Map[][];
int n;
int startx;
int starty;
int t;
int sum;
int temp;
char s[];
int minn;
cin>>t;
while(t--)
{
temp=inf;
memset(a,,sizeof(a));
sum=;
memset(Map,inf,sizeof(Map));
memset(dist,inf,sizeof(dist));
cin>>n>>startx>>starty;
for(int i=;i<=n;i++)
{
cin>>s;
for(int j=;j<=;j++)
{
a[i][s[j]-'']++;
}
}
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
{
if(i==j)
Map[i][j]=;
else
Map[i][j]=inf;
}
for(int i=;i<=n;i++)
{
for(int j=i+;j<=n;j++)
{
sum=;
for(int k=;k<=;k++)
{
sum+=min(a[i][k],a[j][k]);
}
if(sum==)
{
Map[i][j]=;Map[j][i]=;
}
}
}
for(int i=;i<=n;i++)
dist[i]=Map[startx][i];
memset(visit,,sizeof(visit));
visit[startx]=;
for(int i=;i<=n-;i++)
{
minn=inf;
for(int j=;j<=n;j++)
{
if(visit[j]==&&dist[j]<minn)
{
temp=j;minn=dist[j];
}
}
if(temp==inf)
break;
visit[temp]=;
for(int k=;k<=n;k++)
{
if(Map[temp][k]<inf)
{
if(dist[k]>dist[temp]+Map[temp][k])
dist[k]=dist[temp]+Map[temp][k];
}
}
}
if(dist[starty]==inf)
cout<<"-1\n";
else
cout<<dist[starty]<<endl;
}
return ;
}
上一篇:第八届蓝桥杯 4、方格分割 DFS


下一篇:TensorFlow 辨异 —— tf.add(a, b) 与 a+b(tf.assign 与 =)、tf.nn.bias_add 与 tf.add(转)