记录编号	236694	评测结果	AAAAAATTTT
题目名称	[SDOI 2012]象棋	最终得分	60
用户昵称	Satoshi	是否通过	未通过
代码语言	C++	运行时间	5.011 s
提交时间	2016-03-15 10:31:09	内存使用	6.21 MiB

#include <fstream>
#include <algorithm>
#include <queue>
#include <vector>
#define N 1010
using namespace std;
ifstream in("chessc.in");
ofstream out("chessc.out");
int X,Y,xx,yy;
int n,m;
bool zhang[N][N]={0};//障碍相关
bool l[N][N]={0};//最短路相关
int f[N][N]={0};//最短路相关
int INF=(1<<28);
int dir[4][2]={{1,1},{1,-1},{-1,1},{-1,-1}};//向量
bool vis[2*N]={0};int dis[2*N]={0},del[2*N]={0},pre[2*N]={0};vector<int> G[2*N];//费用流
class edge
{
public:
	int u,v,w,cap,flow;
	void make(int a,int b,int c,int d,int e)
	{
		u=a;v=b;w=c;cap=d;flow=e;
	}
};
vector<edge> E;
class point
{
public:
	int x,y;
	void make(int a,int b)
	{
		x=a;
		y=b;
	}
	void print()
	{
		out<<x<<' '<<y<<endl;
	}
}A[N],B[N];
point operator +(point a,point b)
{
	point c;
	c.x=a.x+b.x;
	c.y=a.y+b.y;
	return c;
}
bool legal(point a)
{
	if(a.x>=1&&a.x<=X&&a.y>=1&&a.y<=Y)if(!zhang[a.x][a.y])return 1;
	return 0;
}
void SPFA(point s)
{
	int i,j,sum=0;
	point u,v;
	queue<point > q;
	for(i=1;i<=X;i++)for(j=1;j<=Y;j++)l[i][j]=0;
	for(i=1;i<=X;i++)for(j=1;j<=Y;j++)f[i][j]=INF;
	f[s.x][s.y]=0;
	q.push(s);
	while(!q.empty())
	{
		u=q.front();
		q.pop();
		l[u.x][u.y]=1;
		for(i=0;i<=3;i++)
		{
			v.x=u.x+dir[i][0]*xx;
			v.y=u.y+dir[i][1]*yy;
			if(legal(v))
			{
				if(!l[v.x][v.y])
				{
					l[v.x][v.y]=1;
					f[v.x][v.y]=f[u.x][u.y]+1;
					q.push(v);
				}
			}
		}
		for(i=0;i<=3;i++)
		{
			v.x=u.x+dir[i][0]*yy;
			v.y=u.y+dir[i][1]*xx;
			if(legal(v))
			{
				if(!l[v.x][v.y])
				{
					l[v.x][v.y]=1;
					f[v.x][v.y]=f[u.x][u.y]+1;
					q.push(v);
				}
			}
		}
	}
}
void add(int u,int v,int w,int cap)
{
	edge e;
	e.make(u,v,w,cap,0);
	E.push_back(e);
	e.make(v,u,-w,0,0);
	E.push_back(e);
	int ooxx=E.size();
	G[u].push_back(ooxx-2);
	G[v].push_back(ooxx-1);
}
bool DinicSPFA(int s,int t,int &flow,int &cost)
{
	int i,u,v,w;
	queue<int> q;
	for(i=0;i<=n;i++)dis[i]=INF,vis[i]=0;
	dis[s]=0;vis[s]=1;pre[s]=0;del[s]=INF;
	q.push(s);
	while(!q.empty())
	{
		u=q.front();
		q.pop();
		vis[u]=0;
		for(i=0;i<G[u].size();i++)
		{
			edge e=E[G[u][i]];
			v=e.v;
			if(e.cap>e.flow&&dis[v]>dis[u]+e.w)
			{
				dis[v]=dis[u]+e.w;
				pre[v]=G[u][i];
			    del[v]=min(del[u],e.cap-e.flow);
				if(!vis[v])
				{
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
	if(dis[t]==INF)return 0;
	flow +=del[t];
	cost +=del[t]*dis[t];
	u = t;
	while(u!=s)
	{
		E[pre[u]].flow+=del[t];
		E[pre[u]^1].flow-=del[t];
		u=E[pre[u]].u;
	}
	return 1;
}
int mincost(int s,int t)
{
	int i,ans=0,flow=0,cost=0;
	while(DinicSPFA(s,t,flow,cost));
	return cost;
}
void read()
{
	int i,j;
	char op;
	in>>X>>Y>>n>>xx>>yy;
	for(i=1;i<=X;i++)
	{
		for(j=1;j<=Y;j++)
		{
			in>>op;
			if(op=='*')zhang[i][j]=1;
		}
	}
	for(i=1;i<=n;i++)in>>A[i].x>>A[i].y;
	for(i=1;i<=n;i++)in>>B[i].x>>B[i].y;
	for(i=1;i<=n;i++)
	{
		SPFA(A[i]);
		for(j=1;j<=n;j++)
		{
			add(i,n+j,f[B[j].x][B[j].y],1);
			//w[i][n+j]=w[n+j][i]=inf-f[B[j].x][B[j].y];
		}
	}
	for(i=1;i<=n;i++)add(0,i,0,1);
	for(i=n+1;i<=2*n;i++)add(i,2*n+2,0,1);
	n=2*n+2;
}
void work()
{
	int i;
	int ans=0;
	ans=mincost(0,n);
	out<<ans<<endl;
}
int main()
{
	read();
	work();
	return 0;
}