首页 > 代码库 > UVa 10496 - Collecting Beepers

UVa 10496 - Collecting Beepers

题目:一个机器人从一个起始点出发(只能上、下、左、右运动),经过一些点后回到起点,求总路径最小长度。

分析:图论,搜索。两点间的距离为:abs(x1-x2)+ abs(y1-y2);每个点必须至少经过一次。

            如果存在一个点走过多次,那么他一定在其他两点间的路径上,则这个点可以不经过这么多次;

            因此我们只考虑每个点经过一次的情况即可(可能存在点在某两点路径上),求出全排列,枚举最优解。

说明:过度自信的起源难道是自卑╮(╯▽╰)╭。

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

int  save[3628800][11],temp[11],used[11],Count;
void dfs(int d, int n)
{
	if (d == n) {
		for (int i = 0 ; i < d ; ++ i)
			save[Count][i] = temp[i];
		Count ++;
		return;
	}
	for (int i = 0 ; i < n ; ++ i)
		if (!used[i]) {
			used[i] = 1;
			temp[d] = i;
			dfs(d+1, n);
			temp[d] = i;
			used[i] = 0;
		}
		
}

int x[11],y[11];

int main()
{
	int T,N,M,s_x,s_y,D;
	while (cin >> T)
	while (T --) {
		cin >> N >> M >> s_x >> s_y >> D;
		for (int i = 0 ; i < D ; ++ i)
			cin >> x[i] >> y[i];
		
		Count = 0;
		dfs(0, D);
		
		int Min = 444444;
		for (int i = 0 ; i < Count ; ++ i) {
			int dist = abs(s_x-x[save[i][0]]) + abs(s_y-y[save[i][0]]);
			for (int j = 1 ; j < D ; ++ j)
				dist += abs(x[save[i][j-1]]-x[save[i][j]]) + abs(y[save[i][j-1]]-y[save[i][j]]);
			dist += abs(s_x-x[save[i][D-1]]) + abs(s_y-y[save[i][D-1]]);
			Min = min(Min, dist);
		}
		cout << "The shortest path has length " << Min << endl;
	} 
    return 0;
}


UVa 10496 - Collecting Beepers