Algorithm

USACO Section3.3 camlot

Problem Summary

Given a board with R rows and C columns, a king and some(from zero to R*C) knights, and their moving patterns, compute the minimum number of moves the player must perform to gather them all in the same square.

Specially, whenever the king and any knight are placed in the same square, the player may choose to move the king and the knight together from that point on, as a single knight.

Analysis

  1. If there is no king, we can simply use the shortest path algorithm.
  2. If there is a king but no knight to pick it up, the total cost C2 of gathering is the sum of the distance that each knight must travel and the distance the king must travel.
  3. If the king is picked up by a knight, then the total cost can be seen as C3 = C2 + E. E is the sum of the extra steps the knight who picks up the king took and the steps the king took to meet the knight.
  4. So we only need to compute C2 and E. C2 can be easily calulated by shortest path algorithm. To get E, we can modify the shortest path algorithm, to calculate not noly the distances from a knight to all the squares without picking up the king, but also the steps needed for the knight and the king to meet and go to any square on the board.

Solution

  1. Get the king’s location and calculate the distance between any square on the board and the king.

  2. For each knight, we use the modified shortest path algorithm to calculate the cost to go to any square on the board, and the cost to pick up the king and then go to any square, then update the total cost of the knights to gather and the minimum extra cost to pick up the king and gather.

  3. Find the square with the minimum sum of cost and pickup cost.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <iostream>
#include <fstream>
#include <cstring>
#include <climits>
#include <cmath>
using namespace std;
const int maxn = 32;
const int maxm = 28;
const int maxd = 4000;
const int dir[][2] = {{-1,-2},{-2,-1},{-2,1},{-1,2},{1,-2},{2,-1},{2,1},{1,2}};
int n,m,total,num=0,ans;
struct Coordinate
{
	int x,y;
} king,knight;
int king_dist[maxn][maxm],dist[maxn][maxm][2];
int cost[maxn][maxm],king_cost[maxn][maxm];
int move(int x,int y,int k)
{
	int tx,ty,f=0;
	for(int i=0;i<8;i++)
	{
		tx=x+dir[i][0];
		ty=y+dir[i][1];
		if(tx<1 || ty<1 || tx>n || ty>m) continue;
		if(dist[tx][ty][k]>dist[x][y][k]+1)
		{
			dist[tx][ty][k]=dist[x][y][k]+1;
			f=1;
		}
	}
	if(k==0 && dist[x][y][1]>dist[x][y][0]+king_dist[x][y])
	{
		dist[x][y][1]=dist[x][y][0]+king_dist[x][y];
		if(king_dist[x][y]>f) f=king_dist[x][y];
	}
	return f;
}
void calc_dist(int sx,int sy)
{
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			dist[i][j][0]=dist[i][j][1]=maxd;
	int maxd;
	dist[sx][sy][0]=0;
	maxd=dist[sx][sy][1]=king_dist[sx][sy];
	int flag;
	for(int d=0;d<=maxd;d++)
	{
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
			{
				if(dist[i][j][0]==d)
				{
					flag=move(i,j,0);
					if(d+flag>maxd) maxd=d+flag;
				}
				if(dist[i][j][1]==d)
				{
					flag=move(i,j,1);
					if(d+flag>maxd) maxd=d+flag;
				}
			}
	}
}
int main()
{
	fstream fin("camelot.in",ios::in);
	fstream fout("camelot.out",ios::out);
	int a;
	char b;
	fin>>n>>m;
	fin>>b>>a;
	king.x=a;
	king.y=b-'A'+1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			king_dist[i][j]=king_cost[i][j]=max(abs(i-king.x),abs(j-king.y));
	while(!fin.eof())
	{
		fin>>b>>a;
		if(fin.eof()) break;
		knight.x=a;
		knight.y=b-'A'+1;
		calc_dist(knight.x,knight.y);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
			{
				cost[i][j]+=dist[i][j][0];
				if(dist[i][j][1]-dist[i][j][0]<king_cost[i][j])
					king_cost[i][j]=dist[i][j][1]-dist[i][j][0];
			}
	}
	ans=INT_MAX;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(cost[i][j]+king_cost[i][j]<ans)
				ans=cost[i][j]+king_cost[i][j];
	fout<<ans<<endl;
	fin.close();
	fout.close();
	return 0;
}