Cho wrote:My solution tries all possible visiting orders of the nuts by a DFS with 2 hueristics to cut off. The first one is to cut off if the current cost plus the under-estimated future cost is not less than minimum cost. The second one is not to visit the k-th nut from the i-th nut if there is a j-th nut such that the j-th nut is not visited yet and cost(i->j)+cost(j->k)<=cost(i->k).

I use your method but I got WA. Can anyone help?

Here is my code:

Code: Select all

```
#include <stdio.h>
#include <string.h>
#define Max 21
#define Maxint 2147483647
typedef struct
{
int x,y;
}Node;
Node nut[15];
int Row,Column,used[Max],seq[Max],D[16][16],check[16][16];
char map[Max][Max];
int n,Lx,Ly,min;
int distance(int x1,int y1,int x2,int y2)
{
int x=abs(x1-x2), y=abs(y1-y2);
return (x>y ? x:y);
}
int checkshort(int i,int j)
{
int k,a,b,c;
for(k=0; k<n; k++)
{
if(k==i || k==j ) continue;
a=D[i][k];
b=D[k][j];
c=D[i][j];
if(a+b<=c)
return 0;
}
return 1;
}
void dfs(int i,int k,int v)
/* i: dfs from this node, k:the rank in seq[], v: path length so far */
{
int j,v2,t;
v2=D[seq[k-1]][n];
if(v+v2>=min)
return;
if(k==n+1)
{
v+=v2;
if(v<min) min=v;
return;
}
for(j=0; j<n; j++)
{
if(used[j]) continue;
if(!check[i][j])
{
for(t=0; t<n; t++)
{
if(t==i || t==j) continue;
if(!used[t])
{
t=-1;
break;
}
}
if(t==-1) continue;
}
used[j]=1;
seq[k]=j;
v2=v+D[seq[k]][seq[k-1]];
dfs(j,k+1,v2);
used[j]=0;
}
}
void main()
{
int i,j;
/*freopen("in.txt","r",stdin);*/
while(scanf("%d %d",&Row,&Column)==2)
{
for(i=0; i<Row; i++) scanf("%s",map[i]);
n=0;
for(i=0; i<Row; i++)
for(j=0; j<Column; j++)
{
if(map[i][j]=='L')
{
Lx=i;
Ly=j;
}
else if(map[i][j]=='#')
{
nut[n].x=i;
nut[n++].y=j;
}
}
nut[n].x=nut[n+1].x=Lx; nut[n].y=nut[n+1].y=Ly;
memset(used,0,sizeof(used));
for(i=0; i<=n; i++)
for(j=i+1; j<=n; j++)
D[i][j]=D[j][i]=distance(nut[i].x,nut[i].y,nut[j].x,nut[j].y);
for(i=0; i<=n; i++)
for(j=i+1; j<=n; j++)
check[i][j]=check[j][i]=checkshort(i,j);
min=Maxint;
seq[0]=n;
dfs(n,1,0);
printf("%d\n",min);
}
}
```