自动搬运

查看原文

来自洛谷，原作者为

	GNAQ Good:bye

搬运于2025-08-24 21:53:42，当前版本为作者最后更新于2018-07-18 20:27:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

(我不知道我前面那位哥们怎么跑到如此快的 我猜他是打表过的，因为仅有的一篇题解教唆你去打表。。）

考虑二分图匹配。非常迷的一点是Dinic跑不过但是匈牙利可以。

首先因为斜行不好做，所以处理的时候把棋盘转45°。

然后我们对于每个单位，在原有的攻击范围内添加上一个Bishop的攻击范围，这样可以使得每个单位都不被它攻击。

然后判定哪些格子不会被攻击到，可以二分图匹配了。

建二分图的时候把坐标转换为转45°之后的图再建图。行列匹配。

代码写的很好懂，可以看一下。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<iterator>
#include<queue>
#include<cmath>
#include<vector>
#include<cstdlib>
using namespace std;

struct ed
{
    int pre,to;
}edge[1000010]={0,0};
int at=1,ptr[10010]={0},matchs[10010],vis[10010],ansf;

int n,m,mapsiz;
char mapx[2200][2200]={0};
bool av[2200][2200]={0},l[2200]={0},h[2200]={0};
int pau[2200][2]={0};

int wx[8]={0,-1,-1,-1,0,1,1,1},wy[8]={-1,-1,0,1,1,1,0,-1};
int KX[8]={-1,-2,-2,-1,1,2,2,1},KY[8]={-2,-1,1,2,2,1,-1,-2};

inline void Insert(int fx,int tx)
{
    at++;
	edge[at].pre=ptr[fx];
	edge[at].to=tx;
	ptr[fx]=at;
}

inline bool Find(int x,int src)
{
	for (int prex=ptr[x];prex;prex=edge[prex].pre) if (vis[edge[prex].to]!=src)
	{
		vis[edge[prex].to]=src;
		if (!matchs[edge[prex].to] || Find(matchs[edge[prex].to],src)) { matchs[edge[prex].to]=x; return true; }
	}
	return false;
}

inline void BuildG()
{
	int _x,_y;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++) if (!av[i][j])
		{
			_x=pau[i][0]+j-1; _y=pau[i][1]+j-1;
			if ((!h[_x]) && (!l[_y])) Insert(_x,_y+mapsiz);
		}
}

inline void GoB(int _x,int _y)
{
	av[_x][_y]=true;
	int i=pau[_x][0]+_y-1,j=pau[_x][1]+_y-1;
	h[i]=true; l[j]=true;
}
inline void GoK(int _x,int _y)
{
	GoB(_x,_y);
	for (int w=0;w<=7;w++) av[_x+wx[w]][_y+wy[w]]=true;
}
inline void GoQ(int _x,int _y)
{
	int wayx[4]={0,-1,0,1},wayy[4]={-1,0,1,0};
	GoB(_x,_y);
	for (int w=0;w<=3;w++) for (int i=1;;i++)
	{
		if (mapx[_x+wayx[w]*i][_y+wayy[w]*i]!='.') break;
		av[_x+wayx[w]*i][_y+wayy[w]*i]=true;
	}
}
inline void GoN(int _x,int _y)
{
	GoB(_x,_y);
	for (int w=0;w<=7;w++) if (_x+KX[w]>0 && _y+KY[w]>0) av[_x+KX[w]][_y+KY[w]]=true;
}

int main()
{
	scanf("%d%d",&n,&m);mapsiz=2*max(n,m)-1;
	for (int i=1;i<=n;i++) scanf("%s",mapx[i]+1);
	
	pau[1][0]=1; pau[1][1]=m;
	for (int i=2;i<=n;i++) { pau[i][0]=pau[i-1][0]+1; pau[i][1]=pau[i-1][1]-1; }
	
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
		{
			if (mapx[i][j]=='.') continue;
			switch (mapx[i][j])
			{
				case 'K':
					GoK(i,j);
					break;
				case 'Q':
					GoQ(i,j);
					break;
				case 'R':
					GoQ(i,j);
					break;
				case 'B':
					GoB(i,j);
					break;
				case 'P':
					GoB(i,j);
					break;
				case 'N':
					GoN(i,j);
					break;
			}
		}
	
	BuildG();
	for (int i=1;i<=mapsiz;i++) ansf+=Find(i,i);
	printf("%d\n",ansf);
	return 0;
}