题解 P3882 【[JLOI2008]将军】

· · 题解

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

考虑二分图匹配。非常迷的一点是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;
}