问题重述

我们有一个$R$行$C$列的博物馆大厅网格。每个格子要么是博物馆原有的守卫（用-1表示），要么是一个文物（用一个非负整数T表示）。每个文物的类型T是一个二进制数，表示其关键点的分布。关键点的位置对应于文物周围的12个特定方向（如题目中图示编号1到12）。如果一个文物保留在大厅中，那么它的所有关键点必须被守卫占据（守卫可以覆盖多个文物的关键点）。守卫不能放在文物的位置上，除非将该文物替换为守卫。我们的目标是找到最少需要新增的守卫数量，使得所有保留的文物都满足其关键点被守卫占据。

解决思路

这个问题可以建模为一个集合覆盖问题，其中我们需要选择最少的守卫位置（即某些文物被替换为守卫），使得所有保留的文物的关键点都被覆盖。具体来说：

1. 关键点与文物的关系：每个文物的关键点是其周围12个方向中某些特定的格子（由T的二进制表示决定）。如果一个文物被保留，那么它的所有关键点必须被守卫占据。
2. 守卫的位置选择：守卫可以放在：
   • 原有的守卫位置（这些位置已经固定，不能被改变）。
   • 将某些文物替换为守卫（即在这些位置新增守卫）。
3. 目标：选择最少的文物位置替换为守卫，使得所有未被替换的文物的关键点都被覆盖。

建模为图论问题

这个问题可以转化为二分图的最小点覆盖问题或集合覆盖问题。具体来说：

• 对于每个文物，其关键点必须被守卫占据。因此，我们可以将文物和其关键点之间的关系建模为约束条件。
• 我们需要选择一些格子作为守卫位置（即“覆盖”这些关键点），使得所有保留的文物的关键点都被覆盖。

关键观察：

1. 守卫的选择：守卫只能放在原有守卫的位置或替换文物后的位置。实际上，原有守卫的位置已经固定，无法新增或移除，因此我们只需要考虑将某些文物替换为守卫。
2. 关键点的覆盖：一个守卫可以覆盖多个文物的关键点。因此，我们需要选择一些文物位置替换为守卫，使得这些守卫覆盖所有保留文物的关键点。

具体步骤：

1. 收集所有关键点：对于每个文物，根据其类型T，解析出其所有关键点（即T的二进制表示中为1的位对应的方向）。
   • 对于每个关键点，检查其是否在大厅内（即坐标是否在1≤x≤R和1≤y≤C范围内）。
   • 如果关键点在大厅内且不是原有守卫的位置（即不是-1），则该关键点需要被守卫占据。
2. 关键点的覆盖：对于每个需要被覆盖的关键点，它必须被某个守卫占据。守卫可以位于：
   • 原有守卫的位置（这些已经固定）。
   • 新增守卫的位置（即某些文物被替换为守卫）。
3. 最小化新增守卫：我们需要选择最少的文物位置替换为守卫，使得所有保留文物的关键点都被覆盖。

算法选择

这个问题可以建模为二分图的最小顶点覆盖问题：

• 将需要被覆盖的关键点作为一组顶点。
• 将可以放置守卫的文物位置作为另一组顶点。
• 如果某个文物位置可以覆盖某些关键点（即该文物位置是关键点的位置），则在它们之间连边。
• 我们需要选择最少的文物位置（顶点），使得所有关键点都被覆盖（即每条边至少有一个端点被选中）。

根据König定理，二分图中的最小顶点覆盖等于最大匹配。因此，我们可以使用二分图匹配算法（如匈牙利算法）来解决这个问题。

具体实现步骤

1. 提取所有需要被覆盖的关键点：
   • 对于每个文物（非-1的格子），解析其类型T，得到其关键点。
   • 对于每个关键点，检查其是否在大厅内且不是原有守卫的位置。如果是，则将该关键点加入需要被覆盖的集合。
   • 注意：同一个关键点可能被多个文物需要，但我们只需要覆盖一次。
2. 构建二分图：
   • 左部节点：所有需要被覆盖的关键点（去重后的集合）。
   • 右部节点：所有可以放置新增守卫的位置（即所有非-1的文物位置）。
   • 边：如果某个文物位置（右部节点）是一个关键点（左部节点）的位置，则它们之间有一条边。
3. 计算最小顶点覆盖：
   • 使用匈牙利算法计算二分图的最大匹配。
   • 根据柯尼希定理，最大匹配的值即为最小顶点覆盖的大小。
4. 输出结果：
   • 最小顶点覆盖的值就是需要新增的守卫数量。

标程

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <memory>
#include <cmath>
#include <bitset>
#include <queue>
#include <vector>
#include <stack>
using namespace std;
 
const int MAXN = 2800;
const int INF = (1<<30);
 
#define CLR(x,y) memset(x,y,sizeof(x))
#define MIN(m,v) (m)<(v)?(m):(v)
#define MAX(m,v) (m)>(v)?(m):(v)
#define ABS(x) ((x)>0?(x):-(x))
#define rep(i,x,y) for(i=x;i<y;++i)
 
int dir[12][2]={{-1,-2},{-2,-1},{-2,1},{-1,2},
    {1,2},{2,1},{2,-1},{1,-2},
    {-1,0},{0,1},{1,0},{0,-1}};
int r,c,ind,ans;
int g[MAXN][MAXN];
int tt;
typedef struct{
    int v,next;
}Edge;
Edge edge[MAXN*MAXN];
int net[MAXN];
int pre[MAXN];
bool vt[MAXN];
 
bool _check(const int& x, const int& y )
{
    if( x < 0 || x >= r || y < 0 || y >= c)
        return false;
    return true;
}
void add_edge(const int& u , const int& v)
{
    edge[ind].v = v;
    edge[ind].next = net[u];
    net[u] = ind;
    ++ind;
}
bool dfs(const int& u)
{
    int i,v;
    for( i = net[u]; i != -1; i = edge[i].next){
        v = edge[i].v;
        if( !vt[v] ){
            vt[v] = true;
            if( pre[v] == -1 || dfs(pre[v])){
                pre[v] = u;
                return true;
            }
        }
    }
    return false;
}
void init()
{
    CLR(net,-1);
    CLR(pre,-1);
    CLR(vt,0);
    ind = 0;
    return ;
}
void make_graph()
{
    int i,j,tmp,u,v,x,y,k;
    rep(i,0,r)
        rep(j,0,c){
            rep(k,0,13){
                if( g[i][j] == -1 )
                    continue;
                if(g[i][j] & (1<<k)){
                    x = i + dir[k][0];
                    y = j + dir[k][1];
                    if( !_check(x,y) )
                        continue;
                    if( g[x][y] == -1)
                        continue;
                    u = i*c + j;
                    v = x*c + y;
                    if( (i+j)&1 )
                        add_edge(v,u);
                    else
                        add_edge(u,v);
                }
            }
        }
    return ;
}
int work()
{
    int i,j,u,v,tmp;
    rep(i,0,r)
        rep(j,0,c)
            scanf("%d",&g[i][j]);
    make_graph();
    int cnt = r*c;
    ans = 0;
    rep(i,0,cnt){
        CLR(vt,0);
        if( dfs(i) )
            ++ans;
    }
    printf("%d. %d\n",tt,ans);
    return 0;
}
int main()
{
    tt = 0;
    while(scanf("%d%d",&r,&c)){
        ++tt;
        if( r==0 || c == 0)
            break;
        init();
        work();
    }
    return 0;
}