好吧本来这题可以用最短路跑完的,结果我硬是打了1.5小时的dfs。。。
其实这题并没有那么难,构造一个无向图再跑最短路即可。
我用的dj跑最短路
问题来了
如果(n,n)是无色的,那么图上就没有这个点
可以构造一个变量flag记录点(n,n)是否有颜色
若flag==0,则在地图上新加一个点。
点与点间的路程情况:
相邻且颜色相同,z[i][j]=0;
相邻且颜色不同,z[i][j]=1;
相隔一格且颜色相同,z[i][j]=2;
相隔一格且颜色不同,z[i][j]=3;
∴点i与点j的距离=其颜色差的绝对值+位置差(是否使用膜法)
即
if(abs(x[i]-x[j])+abs(y[i]-y[j])==1)
{
z[i][j]=z[j][i]=abs(col[i]-col[j]);
}
if(abs(x[i]-x[j])+abs(y[i]-y[j])==2)
z[i][j]=z[j][i]=2+abs(col[i]-col[j]);
献上代码:
#include<bits/stdc++.h>
using namespace std;
bool f[1002];
int n,m,x[1002],y[1002],z[1002][1002],col[1002],sta,en,flag,s[1002];
void dj(int k)
{
s[k]=0;
int maxn,t;
for(int i=1;i<=m;i++)
{
maxn=99999999;
for(int j=1;j<=m;j++)
{
if(f[j]==0&&s[j]<maxn)
{
maxn=s[j];
t=j;
}
}
f[t]=1;
for(int j=1;j<=m;j++)
{
s[j]=min(s[t]+z[t][j],s[j]);
}
}
}
int main()
{
//freopen("chess.in","r",stdin);
//freopen("chess.out","w",stdout);
memset(z,1,sizeof(z));
memset(s,1,sizeof(s));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x[i],&y[i],&col[i]);
if(x[i]==1&&y[i]==1)
{
sta=i;
}
if(x[i]==n&&y[i]==n)
{
flag=1;
en=i;
}
}
if(flag==0)
{
en=m+1;
x[en]=y[en]=n;
}
for(int i=1;i<m;i++)
{
for(int j=i+1;j<=m;j++)
{
if(abs(x[i]-x[j])+abs(y[i]-y[j])==1)
{
z[i][j]=z[j][i]=abs(col[i]-col[j]);
}
if(abs(x[i]-x[j])+abs(y[i]-y[j])==2)
z[i][j]=z[j][i]=2+abs(col[i]-col[j]);
}
}
if(flag==0)
{
for(int i=1;i<=m;i++)
{
if(abs(x[i]-x[en])+abs(y[i]-y[en])==1)
{
z[i][en]=z[en][i]=2;
}
}
m++;
}
dj(sta);
if(s[en]<16843009)
cout<<s[en];
else
cout<<-1;
return 0;
}