CodeForces 116B【二分匹配】

思路：

暴力。。我不会呀。。

YY一个二分匹配嘛，然后数组开小了。GG for an hour.

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int cy[110];

int cx[110];

int n,m;

char ma[15][15];

int g[15][15];

int mma[110][110];

int dx[4]={1,-1,0,0};

int dy[4]={0,0,-1,1};

bool vis[110];

int findpath(int u)

{

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

    {

        if(!vis[i]&&mma[u][i])

        {

            vis[i]=1;

            if(cy[i]==-1||findpath(cy[i]))

            {

                cy[i]=u;

                cx[u]=i;

                return 1;

            }

        }

    }

    return 0;

}

int main()

{

	int x,y;

	n=m=0;

	memset(g,0,sizeof(g));

	scanf("%d%d",&x,&y);

	for(int i=0;i<x;i++)

	{

		scanf("%s",ma[i]);

		for(int j=0;j<y;j++)

		{

			if(ma[i][j]=='P')

				g[i][j]=++m;

			if(ma[i][j]=='W')

				g[i][j]=++n;

		}

	}

	for(int i=0;i<x;i++)

	{

		for(int j=0;j<y;j++)

		{

			if(ma[i][j]=='W')

			{

                int ss=g[i][j];

				for(int k=0;k<4;k++)

				{

					int xx=i+dx[k];

					int yy=j+dy[k];

					if(xx<0||yy<0||xx>=x||yy>=y)

                        continue;

					if(ma[xx][yy]=='P')

                    {

                        int tt=g[xx][yy];

                        mma[ss][tt]=1;

                    }

				}

			}

		}

	}

	memset(cx,-1,sizeof(cx));

    memset(cy,-1,sizeof(cy));

    int ans=0;

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

    {

        if(cx[i]==-1)

        {

            memset(vis,0,sizeof(vis));

            ans+=findpath(i);

        }

    }

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

	return 0;

}

/*

3 10

WPPP...PP.

.P...WW..W

.WWP.PP.PW

*/