[P2825][HEOI2016/TJOI2016]游戏

题目链接：

[HEOI2016/TJOI2016]游戏

在 2016 年，佳媛姐姐喜欢上了一款游戏，叫做泡泡堂。 简单的说，这个游戏就是在一张地图上放上若干个炸弹，看是否能炸到对手，或者躲开对手的炸弹。在玩游戏的过程中，小 H 想到了这样一个问题：当给定一张地图，在这张地图上最多能放上多少个炸弹能使得任意两个炸弹之间不会互相炸到。炸弹能炸到的范围是该炸弹所在的一行和一列，炸弹的威力可以穿透软石头，但是不能穿透硬石头。 给定一张 $ n \times m $ 的网格地图:其中 ``*`` 代表空地，炸弹的威力可以穿透，可以在空地上放置一枚炸弹。 ``x`` 代表软石头，炸弹的威力可以穿透，不能在此放置炸弹。``#`` 代表硬石头，炸弹的威力是不能穿透的，不能在此放置炸弹。例如：给出 $ 1 \times 4 $ 的网格地图 `` *xx*``，这个地图上最多只能放置一个炸弹。给出另一个$ 1 \times 4 $ 的网格地图 ``*x#*``，这个地图最多能放置两个炸弹。 现在小 H 任意给出一张 $ n \times m $ 的网格地图，问你最多能放置多少炸弹。 第一行输入两个正整数 $ n, m $，$ n $ 表示地图的行数，$ m $ 表示地图的列数。 接下来输入 $ n $ 行 $ m $ 列个字符，代表网格地图。``*``的个数不超过 $ n \times m $ 个。 输出一个整数 $ a $，表示最多能放置炸弹的个数。

https://www.luogu.com.cn/problem/P2825

「TJOI / HEOI2016」游戏 - 题目 - LibreOJ

在 2016 年，佳媛姐姐喜欢上了一款游戏，叫做泡泡堂。 简单的说，这个游戏就是在一张地图上放上若干个炸弹，看是否能炸到对手，或者躲开对手的炸弹。在玩游戏的过程中，小 H 想到了这样一个问题：当给定一张地图，在这张地图上最多能放上多少个炸弹能使得任意两个炸弹之间不会互相炸到。炸弹能炸到的范围是该炸弹所在的一行和一列，炸弹的威力可以穿透软石头，但是不能穿透硬石头。 给定一张 的网格地图:其中 * 代表空地，炸弹的威力可以穿透，可以在空地上放置一枚炸弹。 x 代表软石头，炸弹的威力可以穿透，不能在此放置炸弹。# 代表硬石头，炸弹的威力是不能穿透的，不能在此放置炸弹。例如：给出 的网格地图 *xx*，这个地图上最多只能放置一个炸弹。给出另一个 的网格地图 *x#* ，这个地图最多能放置两个炸弹。 现在小 H 任意给出一张 的网格地图，问你最多能放置多少炸弹。

https://loj.ac/problem/2057

题解：

[ZJOI2007]矩阵游戏

小 Q 是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏――矩阵游戏。矩阵游戏在一个 $n \times n$ 黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。每次可以对该矩阵进行两种操作： - 行交换操作：选择矩阵的任意两行，交换这两行（即交换对应格子的颜色）。 - 列交换操作：选择矩阵的任意两列，交换这两列（即交换对应格子的颜色）。 游戏的目标，即通过若干次操作，使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑色。 对于某些关卡，小 Q 百思不得其解，以致他开始怀疑这些关卡是不是根本就是无解的！于是小 Q 决定写一个程序来判断这些关卡是否有解。 **本题单测试点内有多组数据**。 第一行包含一个整数 $T$，表示数据的组数，对于每组数据，输入格式如下： 第一行为一个整数，代表方阵的大小 $n$。 接下来 $n$ 行，每行 $n$ 个非零即一的整数，代表该方阵。其中 $0$ 表示白色，$1$ 表示黑色。 对于每组数据，输出一行一个字符串，若关卡有解则输出 `Yes`，否则输出 `No`。 2 2 0 0 0 1 3 0 0 1 0 1 0 1 0 0 #### 数据规模与约定 - 对于 $20\%$ 的数据，保证 $n \leq 7$。 - 对于 $50\%$ 的数据，保证 $n \leq 50$。 - 对于 $100\%$ 的数据，保证 $1 \leq n \leq 200$，$1 \leq T \leq 20$。

https://www.luogu.com.cn/problem/P1129

#***
*#**
**#*
xxx#

#111
2#22
33#3
xxx#

#111
2#33
44#5
xxx#

//File: P2825.cpp
//Author: yanyanlongxia
//Date: 2020/8/10
//
#include <bits/stdc++.h>
using namespace std;
int n,m,ntot,mtot,tot,head[3000],nxt[3000],ver[3000],row[60][60],col[60][60],match[3000],ans;
bool vis[3000];
void add(int x,int y)//链式前向星加边
{
    ver[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
bool find(int x)//匈牙利算法
{
    for(int i=head[x];i;i=nxt[i])
    {
        int y=ver[i];
        if(!vis[y])
        {
            vis[y]=true;
            if(!match[y] || find(match[y]))
            {
                match[y]=x;
                return true;
            }
        }
    }
    return false;
}
int main() {
    scanf("%d%d",&n,&m);
    char s[60][60];
    bool flag=1;//注意第一次需要单开一行
    pair<int,int>last;//与动态规划的思想相似，每个点所在的抽象出的行的编号都可以由上一个有编号的点转移过来
    for(int i=1;i<=n;i++)
    {
        scanf("%s",(s[i]+1));
        for(int j=1;j<=m;j++)
        {
            if(s[i][j]=='#')//下一次另开一行（抽象意义上的行）
            {
                flag=1;
                continue;
            }
            if(flag==0)//不需要加1
            {
                if(s[i][j]!='x')
                {
                    row[i][j]=row[last.first][last.second];//row数组的意义为该点所在的抽象的行的编号
                    last=make_pair(i,j);
                }
            } else
                if(s[i][j]!='x')
                {
                    row[i][j]=row[last.first][last.second]+1;
                    ntot++;
                    last=make_pair(i,j);
                    flag=0;//当前的加处理完毕
                }
        }
        flag=1;//换行一定要加一
    }
    flag=1;
    last=make_pair(0,0);//清零，赋初值
    for(int i=1;i<=m;i++)//列的处理，与行相似，但是i与j要取反
    {
        for(int j=1;j<=n;j++)
        {
            if(s[j][i]=='#')
            {
                flag=1;
                continue;
            }
            if(flag==0)
            {
                if(s[j][i]!='x')
                {
                    col[j][i]=col[last.second][last.first];//col数组与row数组的意义相似，是列的编号
                    last=make_pair(i,j);
                }
            } else
                if(s[j][i]!='x')
                {
                    col[j][i]=col[last.second][last.first]+1;
                    mtot++;
                    last=make_pair(i,j);
                    flag=0;
                }
        }
        flag=1;
    }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            if (s[i][j]=='*')
                add(row[i][j],col[i][j]);//加边
        }
    for (int i = 1; i <= ntot; ++i) {
        memset(vis,0,sizeof(vis));
        if(find(i))
            ans++;//统计最大匹配
    }
    printf("%d\n",ans);
    return 0;
}