题目大意：大厅每个位置都有一个文物或者一个守卫，文物是安全的前提是： 关键位置上必须有一个守卫，或者文物本身的位置上有一个守卫。求保证每个文物是安全的守卫的最少数量。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int map[55][55];
int xid[5555];
int yid[5555];
struct node{int u,v;};
node edge[755555];
int first[75555],next[755555];
int vis[55555];
int cc,n,m,x_id,y_id;
int linker[55555];
int xx[12]={-1,-2,-2,-1,1,2,2,1,-1,0,1,0};
int yy[12]={-2,-1,1,2,2,1,-1,-2,0,1,0,-1};
inline void add_edge(int u,int v){
edge[cc].u=u;
edge[cc].v=v;
next[cc]=first[u];
first[u]=cc;
cc++;
}
bool dfs(int u){
int i;
for(i=first[u];i!=-1;i=next[i]){
int v=edge[i].v;
if(!vis[v]){
vis[v]=1;
if(linker[v]==-1||dfs(linker[v])){
linker[v]=u;
return true;
}
}
}
return false;
}
int match(int n){
int i;
int res=0;
memset(linker,-1,sizeof(linker));
for(i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
if(dfs(i))
res++;
}
return res;
}
void bfind(int mm){
int x=mm/m;
int y=mm%m;
int i;
if(map[x][y]==-1)return ;
for(i=0;i<12;i++){
if((1<<i)&map[x][y]){
int nx=x+xx[i];
int ny=y+yy[i];
if(nx>=n||nx<0||ny>=m||ny<0)
continue;
if(map[nx][ny]==-1)
continue;
if((x+y)%2==0)
add_edge(xid[mm],x_id-1+yid[nx*m+ny]);
else
add_edge(xid[nx*m+ny],x_id-1+yid[mm]);
}
}
}
int main(){
int cas=0;
while(scanf("%d%d",&n,&m)!=EOF){
if(n==0&&m==0)break; cas++;
int i,j; x_id=y_id=1,cc=0;
memset(xid,0,sizeof(xid));
memset(yid,0,sizeof(yid));
memset(first,-1,sizeof(first));
memset(next,-1,sizeof(next));
for(i=0;i<n;i++){
for(j=0;j<m;j++){
scanf("%d",&map[i][j]);
int x=i*m+j;
if((i+j)%2==0)xid[x]=x_id++;
else yid[x]=y_id++;
}
}
for(i=0;i<n;i++)for(j=0;j<m;j++)bfind(i*m+j);
int res=match(x_id-1);
printf("%d. %d
",cas,res);
}
return 0;
}