P3355 骑士共存问题

传送门

分析

由题可知，有很多种元素。例如：马的走法，有障碍物……

那么就需要分别讨论，找到题的共性来解决。

问题特性

不难发现，只要将网格标记后就行了。因为都是马，也只有马。所以如果一个方格被标记，就不能放马。同理，如果一个个并未标记，那么一定可以放马。

马的走法

o x o x o
x o o o x
o o m o o
x o o o x
o x o x o

其中 $m$ 代表马，$x$ 代表不能走的地方。
再多举几个例子，通过上面问题特性的判断，在画一个图。

x m x m x
m x m x m
x m x m x
m x m x m
x m x m x

不难发现一些显而易见的规律了。但是仍然会有一些差别，如下：

情况 1：

x m x m x
m x m x m
x m x m x
m x m x m
x m x m x

和：

情况 2

m x m x m
x m x m x
m x m x m
x m x m x
m x m x m

就有本质上的差别。马的数量是有差别的。

所以，在没有就障碍的情况下，最优解为：

$n$ 为棋盘大小。

$n\mod2==0$ 时 $ans=\frac{n^2}{2}$;

$n\mod2==1$ 时 $ans=\frac{n^2}{2}+1$;

A*

搜索，但对于每种路径有一个期望，若搜索路径过程中，消费大于期望，则放弃本路径。从而提升效率。

A*算法注意

注意，障碍的地方不能放士兵！！！所以个能会有空白，只要是空白一定可以放士兵，但记得的更新当前的值。

最重要的是不知道现在是情况一和情况二那个多，所以最好进行一次比较。确保最优解。记得方法合理即可，以防TLE。

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstdio>
#include<cctype>
#include<queue>
#include<iostream>
#include<cstdio>
using namespace std;
const int N=200005;
const int M=2000010;
const int ma_am=1000000010;
int n,m,s,t,ans;
struct edge{
  int adj,nex,fw;
}e[M];
int g[N],top=1;
void add(int x,int y,int z){
  e[++top]=(edge){y,g[x],z};
  g[x]=top;
}
int dep[N],cur[N];
bool vis[N];
queue<int> Q;
bool b_b(){
  for(int i=1;i<=n;i++)
    vis[i]=0,cur[i]=g[i];
  Q.push(s),vis[s]=1,dep[s]=0;
  while(Q.size()){
    int x=Q.front(); Q.pop();
    for(int i=g[x];i;i=e[i].nex){
      int to=e[i].adj;
      if(!vis[to]&&e[i].fw){
        vis[to]=1;
        dep[to]=dep[x]+1;
        Q.push(to);
      }
    }
  }
  return vis[t];
}
int d_d(int x,int F){
  if(!F||x==t)
    return F;
  int flow=0,f;
  for(int i=cur[x];i;i=e[i].nex){
    int to=e[i].adj; cur[x]=i;
    if(dep[x]+1==dep[to]&&
    (f=d_d(to,min(F,e[i].fw)))>0){
      e[i].fw-=f;
      e[i^1].fw+=f;
      flow+=f,F-=f;
      if(!F) break;
    }
  }
  return flow;
}
int p(int x,int y){return (x-1)*n+y;}
bool G[210][210];
int tx[9]={1,1,2,2,-1,-1,-2,-2};
int ty[9]={-2,2,-1,1,-2,2,-1,1};
int main(){
  scanf("%d%d",&n,&m);
  for(int i=1,x,y;i<=m;i++){
    scanf("%d%d",&x,&y);
    G[x][y]=1;
  }
  for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++){
      if(G[i][j]) continue;
      if((i+j)&1){
        add(1,p(i,j)+1,1);
        add(p(i,j)+1,1,0);
        for(int k=0;k<8;k++){
          int xt=tx[k]+i,yt=ty[k]+j;
          if(xt<1||xt>n||yt<1||yt>n||G[xt][yt])
            continue;
          add(p(i,j)+1,p(xt,yt)+1,ma_am);
          add(p(xt,yt)+1,p(i,j)+1,0);
        }
      } else add(p(i,j)+1,n*n+2,1),
        add(n*n+2,p(i,j)+1,0);
    }
  ans=n*n-m,s=1,n=t=n*n+2;
  while(b_b()) ans-=d_d(s,ma_am);
  printf("%d\n",ans);
  return 0;
}