gistfile1.cpp

#include <fstream>
#include <cmath>
using namespace std;
void BFS(int , int ,int dist[26][30]);
int col,row;
//char square[30][26];
int  allk[26][30];
int  pickup[26][30];
int maxx(int i , int j)
{
	if (i>=j)
		return i;
	else
		return j;

}
int minx(int i,int j)
{
	if(i>=j)
		return j;
	else 
		return i;
}
class point
{
public:
	int x,y,d;
};
point  queue[781];

int  q_begin,q_size;

point  knight[781];
int nknight;

point king;
int main()
{
	ifstream fin("camelot.in");
	ofstream fout("camelot.out");
	fin>>row>>col;
	char x;
	int  y;
	fin>>x>>y;
	king.x = x- 'A' ;
	king.y = y-  1;
	while(!fin.eof())
	{
		fin>>x>>y;
		knight[nknight].x = x-'A';
		knight[nknight].y = y-1;
		nknight++;
	}
	nknight--;
	//
	if (!nknight)
	{
		fout<<0<<endl;return 0;
	}
	int minsum = 0x7fffffff;
	for ( int i = 0 ; i<col ; i++ )
	{
		for ( int j = 0 ; j<row ; j++ )
		{
			
			BFS(i,j,allk);
			
			
			int kpick;
			for ( int ii = maxx(king.x-2,0) ; ii<minx(king.x+3,col); ii++)
			{
				for ( int jj = maxx(king.y-2,0) ; jj<minx(king.y+3,row); jj++)
				{	
					BFS(ii,jj,pickup);
					int sum=0;
					for (int k = 0 ; k<nknight ;k++)
					{
						sum+= allk[knight[k].x][knight[k].y];
					}
					if (sum>minsum)
					{
						continue;
					}

					for (int kpick = 0 ; kpick<nknight ; kpick++)
					{
						int temp = allk[ii][jj] + maxx(abs(king.x-ii),abs(king.y-jj))+pickup[knight[kpick].x][knight[kpick].y];
						
						
						sum -= allk[knight[kpick].x][knight[kpick].y];
						
						temp+=sum;
						

						if (temp<minsum)
						{
							minsum = temp;
						}
						sum += allk[knight[kpick].x][knight[kpick].y];

					}
			
				}
			}
			
			
		}
	}
	fout<<minsum<<endl;
	fin.close();
	fout.close();
	return 0;
}

void BFS(int i, int j,int dist[26][30])
{
	for (int i = 0 ; i<col;i++)
	{
		for (int j = 0 ; j<row;j++)
		{
			dist[i][j] = 0x7fff;
		}
	}
	q_begin=0;
	q_size=0;
	queue[0].d = 0;
	queue[0].x = i;
	queue[0].y = j;
	dist[i][j] = 0;
	q_size++;
	int x,y,d;
	
	for (int k = q_begin; k<q_size ;k++)
	{
		x = queue[k].x;
		y = queue[k].y;
		d = queue[k].d;
		//
		if (x+1<col&&y+2<row&&dist[x+1][y+2]==0x7fff)
		{
			dist[x+1][y+2] = d+1;
			queue[q_size].x = x+1;
			queue[q_size].y = y+2;
			queue[q_size].d = d+1;
			q_size++;
		}
 		if (x+2<col&&y+1<row&&dist[x+2][y+1]==0x7fff)
		{
			dist[x+2][y+1] = d+1;
			queue[q_size].x = x+2;
			queue[q_size].y = y+1;
			queue[q_size].d = d+1;
			q_size++;
		}
		if (x+2<col&&y-1>=0&&dist[x+2][y-1]==0x7fff)
		{
			dist[x+2][y-1] = d+1;
			queue[q_size].x = x+2;
			queue[q_size].y = y-1;
			queue[q_size].d = d+1;
			q_size++;
		}
		if (x+1<col&&y-2>=0&&dist[x+1][y-2]==0x7fff)
		{
			dist[x+1][y-2] = d+1;
			queue[q_size].x = x+1;
			queue[q_size].y = y-2;
			queue[q_size].d = d+1;
			q_size++;
		}
		if (x-1>=0&&y-2>=0&&dist[x-1][y-2]==0x7fff)
		{
			dist[x-1][y-2] = d+1;
			queue[q_size].x = x-1;
			queue[q_size].y = y-2;
			queue[q_size].d = d+1;
			q_size++;
		}
		if (x-2>=0&&y-1>=0&&dist[x-2][y-1]==0x7fff)
		{
			dist[x-2][y-1] = d+1;
			queue[q_size].x = x-2;
			queue[q_size].y = y-1;
			queue[q_size].d = d+1;
			q_size++;
		}
		if (x-2>=0&&y+1<row&&dist[x-2][y+1]==0x7fff)
		{
			dist[x-2][y+1] = d+1;
			queue[q_size].x = x-2;
			queue[q_size].y = y+1;
			queue[q_size].d = d+1;
			q_size++;
		}
		if (x-1>=0&&y+2<row&&dist[x-1][y+2]==0x7fff)
	    {
			dist[x-1][y+2] = d+1;
			queue[q_size].x = x-1;
			queue[q_size].y = y+2;
			queue[q_size].d = d+1;
			q_size++;
		}
		//	
		
	}

}