[JLOI2008]将军

Description

刘先生最近在学习国际象棋，使用一个叫”jloi-08”的游戏软件。在这个游戏里，不但可以和电脑普通地对弈，还可以学习著名的棋局，还有针对初学者的规则指导等丰富功能。但是…大小却要1.4G T_T。

言归正传，在这个软件里，为了让玩家更好地理解和运用各个棋子，有很多趣味的游戏，比如以下就是一个：

给出一个棋盘和一些棋子，让你把这些棋子摆放在棋盘上，使得两两不互相攻击。你的得分由你摆放上去的棋子的个数与种类有关。

这个游戏很复杂，刘先生老是玩不到高分。于是电脑便降低了难度，替刘先生摆上了一些棋子，最后只给你任意多个bishop(教主)。

现在刘先生便要考一考你，在电脑给出的这张棋盘上，最多能放几个bishop。

国际象棋中一共有6种棋子：

king     (国王)

queen   (皇后)

bishop  (教主)

knight  (骑士)

rook    (车)

pawn   (步兵)

queen和knight不用说了；rook攻击水平和垂直两条线上的所有格子；pawn攻击前方两条斜线方向各一格；king攻击周围8个方向各1格；bishop攻击两条对角线上的所有格子。

除knight以外，所有棋子的攻击范围均会被别的棋子所阻挡。(“前方”指x递增的方向，x行y列)

可惜的是这个软件也不是顶优秀，给出的棋盘上的棋子可能互相会攻击，不过你不用理会这些，你只要保证你摆放的bishop不与它们以及不互相攻击就可以了。

Input

第一行是2个整数x, y(1<=x,y<=1024)，

下面的x行每行y个字符表示棋盘，

其中：K – king, Q – queen, B – bishop, N – knight, R – rook, P – pawn, “.” – blank.

Output

仅一行一个数，表示最多能够摆放的bishop的个数。

Sample Input

3 3

..N

...

...

Sample Output

2

恶心的大模拟……还好玩过国际象棋

预处理出原本的棋子能攻击的所有的点，然后由于bishop的攻击的斜线攻击，于是我们将棋盘旋转45°，再横竖划分，连边跑最大匹配即可

/*program from Wolfycz*/

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define inf 0x7f7f7f7f

using namespace std;

typedef long long ll;

typedef unsigned int ui;

typedef unsigned long long ull;

inline char gc(){

	static char buf[1000000],*p1=buf,*p2=buf;

	return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;

}

inline int frd(){

	int x=0,f=1; char ch=gc();

	for (;ch<'0'||ch>'9';ch=gc())	if (ch=='-')	f=-1;

	for (;ch>='0'&&ch<='9';ch=gc())	x=(x<<3)+(x<<1)+ch-'0';

	return x*f;

}

inline int read(){

	int x=0,f=1; char ch=getchar();

	for (;ch<'0'||ch>'9';ch=getchar())	if (ch=='-')	f=-1;

	for (;ch>='0'&&ch<='9';ch=getchar())	x=(x<<3)+(x<<1)+ch-'0';

	return x*f;

}

inline void print(int x){

	if (x<0)	putchar('-'),x=-x;

	if (x>9)	print(x/10);

	putchar(x%10+'0');

}

const int N=1<<10,M=1<<20;

bool l[(N<<1)+10],r[(N<<1)+10];//l:\ r:/

bool can[N+10][N+10];

char map[N+10][N+10];

int pre[M+10],now[(N<<1)+10],child[M+10];

int path[(N<<1)+10],vis[(N<<1)+10];

int tot,Time,n,m,Ans;

bool in_map(int x,int y){return x>0&&x<=n&&y>0&&y<=m;}

void join(int x,int y){pre[++tot]=now[x],now[x]=tot,child[tot]=y;}

bool Extra(int x){

	for (int p=now[x],son=child[p];p;p=pre[p],son=child[p]){

		if (vis[son]==Time)	continue;

		vis[son]=Time;

		if (!~path[son]||Extra(path[son])){

			path[son]=x;

			return 1;

		}

	}

	return 0;

}

void solve_King(int x,int y){

	for (int i=-1;i<=1;i++){

		for (int j=-1;j<=1;j++){

			int tx=x+i,ty=y+j;

			if (!in_map(tx,ty))	continue;

			can[tx][ty]=1;

		}

	}

}

void solve_Pawn(int x,int y){

	for (int i=-1;i<=1;i++){

		for (int j=-1;j<=1;j++){

			if (!i||!j)	continue;

			int tx=x+i,ty=y+j;

			if (!in_map(tx,ty))	continue;

			can[tx][ty]=1;

		}

	}

}

void solve_Rook(int x,int y){

	for (int i=x-1;i>=1;i--){

		if (map[i][y]!='.')	break;

		can[i][y]=1;

	}

	for (int i=x+1;i<=n;i++){

		if (map[i][y]!='.')	break;

		can[i][y]=1;

	}

	for (int j=y-1;j>=1;j--){

		if (map[x][j]!='.')	break;

		can[x][j]=1;

	}

	for (int j=y+1;j<=n;j++){

		if (map[x][j]!='.')	break;

		can[x][j]=1;

	}

}

void solve_Queen(int x,int y){solve_Rook(x,y);}

const int dx[8]={-2,-2,-1,-1,1,1,2,2};

const int dy[8]={-1,1,-2,2,-2,2,-1,1};

void solve_Knight(int x,int y){

	for (int k=0;k<8;k++){

		int tx=x+dx[k],ty=y+dy[k];

		if (!in_map(tx,ty))	continue;

		can[tx][ty]=1;

	}

}

int main(){

	memset(path,255,sizeof(path));

	n=read(),m=read();

	for (int i=1;i<=n;i++){

		scanf("%s",map[i]+1);

		for (int j=1;j<=m;j++)

			if (map[i][j]!='.')

				l[i-j+m]=1,r[i+j-1]=1;

	}

	for (int i=1;i<=n;i++){

		for (int j=1;j<=m;j++){

			if (map[i][j]=='K')	solve_King(i,j);

			if (map[i][j]=='P')	solve_Pawn(i,j);

			if (map[i][j]=='R')	solve_Rook(i,j);

			if (map[i][j]=='Q')	solve_Queen(i,j);

//			if (map[i][j]=='B')	solve_Bishop(i,j);

			if (map[i][j]=='N')	solve_Knight(i,j);

		}

	}

	for (int i=1;i<=n;i++){

		for (int j=1;j<=m;j++){

			if (can[i][j]|l[i-j+m]||r[i+j-1])	continue;

			join(i-j+m,i+j-1);

		}

	}

	for (int i=1;i<n+m;i++){

		++Time;

		if (Extra(i))	Ans++;

	}

	printf("%d\n",Ans);

	return 0;

}

巴特西

[JLOI2008]将军

最新文章

热门文章