Analysis
这道题跟前几道题差不多，依旧是匈牙利算法求二分图匹配，在连边的时候，要连两个矛盾的位置（即一个骑士和其控制的位置）。然后就跑一遍匈牙利算法就好了。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define maxn 110 6 using namespace std; 7 inline int read() 8 { 9 int x=0; 10 bool f=1; 11 char c=getchar(); 12 for(; !isdigit(c); c=getchar()) if(c=='-') f=0; 13 for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+c-'0'; 14 if(f) return x; 15 return 0-x; 16 } 17 inline void write(int x) 18 { 19 if(x<0){putchar('-');x=-x;} 20 if(x>9)write(x/10); 21 putchar(x%10+'0'); 22 } 23 struct node 24 { 25 int to,nex; 26 }edge[20*(maxn*maxn+10)]; 27 int n,m,t,cnt,ans; 28 int head[20*(maxn*maxn+10)],match[20*(maxn*maxn+10)]; 29 bool map[maxn*10][maxn*10],book[20*(maxn*maxn+10)]; 30 int dir1[10]={0,1,-1,1,-1,2,-2,2,-2},dir2[10]={0,2,2,-2,-2,1,1,-1,-1}; 31 inline void add(int x,int y) 32 { 33 cnt++; 34 edge[cnt].to=y; 35 edge[cnt].nex=head[x]; 36 head[x]=cnt; 37 } 38 inline bool dfs(int u) 39 { 40 for(int i=head[u];i;i=edge[i].nex) 41 { 42 int v=edge[i].to; 43 if(!book[v]) 44 { 45 book[v]=1; 46 if(!match[v]||dfs(match[v])) 47 { 48 match[v]=u; 49 return true; 50 } 51 } 52 } 53 return false; 54 } 55 inline int calculation(int x,int y){return m*(x-1)+y;} 56 int main() 57 { 58 n=read();m=read();t=read(); 59 for(int i=1;i<=t;i++) 60 { 61 int x,y; 62 x=read();y=read(); 63 map[x][y]=1; 64 } 65 for(int i=1;i<=n;i++) 66 for(int j=1;j<=m;j++) 67 if(!map[i][j]) 68 { 69 for(int k=1;k<=8;k++) 70 { 71 int mi=i+dir1[k],mj=j+dir2[k]; 72 if(mi>0&&mj>0&&mi<=n&&mj<=m&&!map[mi][mj]&&(mi+mj)%2==1) 73 { 74 add(calculation(i,j),calculation(mi,mj)); 75 } 76 } 77 } 78 for(int i=1;i<=calculation(n,m);i++) 79 { 80 memset(book,0,sizeof(book)); 81 if(dfs(i))ans++; 82 } 83 write(n*m-ans-t); 84 return 0; 85 }
请各位大佬斧正（反正我不认识斧正是什么意思）