记录编号	235423	评测结果	AAAAAAAAAA
题目名称	[SDOI 2012]象棋	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	0.492 s
提交时间	2016-03-10 19:21:12	内存使用	2.48 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
using namespace std;
const int inf = 1e8/400;
const int maxn = 205;
const int maxk = 505;


int n, m, k, a, b;
bool visx[maxk];
bool visy[maxk];
int slack[maxk];
int links[maxk];
int lx[maxk];
int ly[maxk];
int v[maxk][maxk];
int ma[maxk][maxk];
int be[maxk], en[maxk];
int nx, ny;


bool hungary(int now) {
	int sum;
	visx[now] = true;
	for(int i = 1; i <= ny; i++) {
		if(visy[i]) continue;
		sum = lx[now]+ly[i]-v[now][i];
		if(sum) {
			slack[i] = min(slack[i], sum);//找到次小的路径加入可增广队列 
			continue;
		}
		visy[i] = true;
		if(links[i] == -1 || hungary(links[i])) {//如果可以增广 
			links[i] = now;
			return true;
		}
	}
	return false;
} 

int km() {
	int d;
	int ans = 0;
	for(int i = 1; i <= nx; i++) {
		lx[i] = -inf;
		for(int j = 1; j <= ny; j++) {
			lx[i] = max(lx[i], v[i][j]);//先初始化lx为所有连接lx边中的最大值 
		}
	}
	memset(links, -1, sizeof(links));
	memset(ly, 0, sizeof(ly));
	for(int i = 1; i <= nx; i++) {
		for(int j = 1; j <= ny; j++) {
			slack[j] = inf;
		} 
		while(true) {
			memset(visx, false, sizeof(visx));
			memset(visy, false, sizeof(visy));
			if(hungary(i)) break;
			d = inf;
			for(int j = 1; j <= ny; j++) {
				if(visy[j]) continue;//没被访问过的y才有可增广值
				 d = min(d, slack[j]);
			}
			for(int j = 1; j <= max(nx, ny); j++) {
				if(visx[j]) lx[j] -= d;
				if(visy[j]) ly[j] += d;
			}
		}
	}
	for(int i = 1; i <= ny; i++) {
		if(links[i] == -1) continue;
		ans += v[links[i]][i];
	}
	return ans;
}

const int base = 1e3;

int dis[maxn][maxn];
int handle[10];
bool vis[maxn][maxn];

bool updata(int fx, int fy, int tx, int ty) {
	if(tx < 1 || ty < 1 || tx > n || ty > m || !ma[tx][ty]) return false;
	if(!vis[tx][ty]) {
		 dis[tx][ty] = dis[fx][fy]+1; 
		 vis[tx][ty] = true;
		 return true;
	}
	return false;
}

void make_graph() {
	for(int i = 1; i <= k; i++) {
		queue<pair<int,int> > q;
		while(q.size()) q.pop(); 
		q.push(make_pair(be[i]/base, be[i]%base));
		for(int j = 1; j <= n; j++) {
			for(int l = 1; l <= m; l++) {
				dis[j][l] = inf;
				vis[j][l] = false;
			}
		}
		int nowx, nowy;
		dis[be[i]/base][be[i]%base] = 0;
		while(!q.empty()) {
			nowx = q.front().first;
			nowy = q.front().second;
			q.pop();
//			if(vis[nowx][nowy]) continue;
			vis[nowx][nowy] = true;
			if(updata(nowx, nowy, nowx+a, nowy+b)) q.push(make_pair(nowx+a, nowy+b));
			if(updata(nowx, nowy, nowx+a, nowy-b)) q.push(make_pair(nowx+a, nowy-b));
			if(updata(nowx, nowy, nowx-a, nowy+b)) q.push(make_pair(nowx-a, nowy+b));
			if(updata(nowx, nowy, nowx-a, nowy-b)) q.push(make_pair(nowx-a, nowy-b));
			if(updata(nowx, nowy, nowx+b, nowy+a)) q.push(make_pair(nowx+b, nowy+a));
			if(updata(nowx, nowy, nowx+b, nowy-a)) q.push(make_pair(nowx+b, nowy-a));
			if(updata(nowx, nowy, nowx-b, nowy+a)) q.push(make_pair(nowx-b, nowy+a));
			if(updata(nowx, nowy, nowx-b, nowy-a)) q.push(make_pair(nowx-b, nowy-a));
		}
		for(int j = 1; j <= k; j++) {
			nowx = en[j]/base;
			nowy = en[j]%base;
			v[i][j] = inf-dis[nowx][nowy];
		}
	}
}

void read() {
	scanf("%d %d %d %d %d", &n, &m, &k, &a, &b);
	char tmp[105];
	for(int i = 1; i <= n; i++) {
		scanf("%s",tmp+1);
		for(int j = 1; j <= m; j++) {
			if(tmp[j] == '*') continue;
			ma[i][j] = 1;
		}
	}
	int c, d;
	for(int i = 1; i <= k; i++) {
		scanf("%d %d", &c, &d);
		be[i] = c*1000+d;
	}
	for(int i = 1; i <= k; i++) {
		scanf("%d %d", &c, &d);
		en[i] = c*1000+d;
	}
	nx = ny = k;
}

void solve() {
	make_graph();
	printf("%d",inf*k-km());
}
int main() {
	freopen("chessc.in", "r", stdin);
	freopen("chessc.out", "w", stdout);
	read();
	solve();
	return 0;
}