2091970_wa.c

北大大牛代码 1240道题的原代码 超级权威

# include <stdio.h>
# include <math.h>
# include <string.h>
# include <stdlib.h>

int mark[11];
int n, no;
int x, y;
int min;
struct node
{
	int x;
	int y;
}beeper[11];

void dfs(int n,int ans,int q)
{
	int i, tmp;

	if(q==no)
	{
		if(min>ans+abs(beeper[n].x-x)+abs(beeper[n].y-y))
			min = ans+abs(beeper[n].x-x)+abs(beeper[n].y-y);
		return ;
	}
	if(n!=-1)
		mark[n] = 1;
	for(i = 0; i < no; i++)
	{
		if(mark[i]==0)
		{
			if(n==-1)
				tmp = abs(beeper[i].x-x)+abs(beeper[i].y-y);
			else
				tmp = abs(beeper[i].x-beeper[n].x)+abs(beeper[i].y-beeper[n].y);
			dfs(i,ans+tmp,q+1);
			mark[i] = 0;
		}
	}
}

void input()
{
	int i;
	int r, l;

	while(scanf("%d",&n)==1)
	{
		min = 30000;
		memset(mark,0,sizeof(mark));
		scanf("%d%d%d%d",&r,&l,&x,&y);
		scanf("%d",&no);
		for(i = 0; i < no; i++)
			scanf("%d%d",&beeper[i].x,&beeper[i].y);
		dfs(-1,0,0);
		printf("The shortest path has length %d\n",min);
	}
}

int main()
{
	input();
	return 1;
}