# 棋盘问题总结

[提交][状态][讨论版]

```8 0
```

## 32

```#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define grey 2
#define black 1
#define white 0
int sum,n,m,Map[105][105],color[105][105],num_white,num_black,White[105],Black[10005],used[10005],match[10005];
bool dfs(int u){
int t,i;
for (int v=1;v<=num_white;v++)
{
i=White[v];
if (used[i]==0 && Map[u][i])
{

used[i]=1;
t=match[i];
match[i]=u;
if (t==0 || dfs(t)) return 1;
match[i]=t;
}

}
return 0;
}
void make_way(int u,int v)
{
Map[u][v]=1;
}
int make_num(int a,int b)
{
return ((n)*(a-1)+b);
}
void make_edge()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(color[i][j]!=grey)
{
if(color[i][j]==white)
{
White[++num_white]=make_num(i,j);
}else Black[++num_black]=make_num(i,j);
if(i>1&&color[i-1][j]!=grey) make_way(make_num(i,j),make_num(i-1,j));
if(j>1&&color[i][j-1]!=grey) make_way(make_num(i,j),make_num(i,j-1));
if(i<n&&color[i+1][j]!=grey) make_way(make_num(i,j),make_num(i+1,j));
if(j<m&&color[i][j+1]!=grey) make_way(make_num(i,j),make_num(i,j+1));
}
}
void draw(int n)
{
for(int i=1;i<=n;i++)
{
if(i%2) color[i][1]=black;else color[i][1]=white;
for(int j=2;j<=n;j++)
{
color[i][j]=1^color[i][j-1];
}
}
}
void print()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
cout<<color[i][j];
cout<<endl;
}
}
int main()
{
scanf("%d %d",&n,&m);
draw(n);
int a,b;
for(int i=1;i<=m;i++)
scanf("%d %d",&a,&b),color[a][b]=grey;
make_edge();
//print();
for(int i=1;i<=num_black;i++)
{
memset(used,0,sizeof(used));
if(dfs(Black[i]))sum++;
//cout<<Black[i]<<endl;
}
cout<<sum<<endl;
}```
```#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define grey 2
#define black 1
#define white 0
int sum,n,m,Map[105][105],color[105][105],num_white,num_black,White[105],Black[10005],used[10005],match[10005];
bool dfs(int u){
int t,i;
for (int v=1;v<=num_white;v++)
{
i=White[v];
if (used[i]==0 && Map[u][i])
{

used[i]=1;
t=match[i];
match[i]=u;
if (t==0 || dfs(t)) return 1;
match[i]=t;
}

}
return 0;
}
void make_way(int u,int v)
{
Map[u][v]=1;
}
int make_num(int a,int b)
{
return ((n)*(a-1)+b);
}
void make_edge()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(color[i][j]!=grey)
{
if(color[i][j]==white)
{
White[++num_white]=make_num(i,j);
}else Black[++num_black]=make_num(i,j);
if(i>1&&color[i-1][j]!=grey) make_way(make_num(i,j),make_num(i-1,j));
if(j>1&&color[i][j-1]!=grey) make_way(make_num(i,j),make_num(i,j-1));
if(i<n&&color[i+1][j]!=grey) make_way(make_num(i,j),make_num(i+1,j));
if(j<m&&color[i][j+1]!=grey) make_way(make_num(i,j),make_num(i,j+1));
}
}
void draw(int n)
{
for(int i=1;i<=n;i++)
{
if(i%2) color[i][1]=black;else color[i][1]=white;
for(int j=2;j<=n;j++)
{
color[i][j]=1^color[i][j-1];
}
}
}
void print()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
cout<<color[i][j];
cout<<endl;
}
}
int main()
{
scanf("%d %d",&n,&m);
draw(n);
int a,b;
for(int i=1;i<=m;i++)
scanf("%d %d",&a,&b),color[a][b]=grey;
make_edge();
//print();
for(int i=1;i<=num_black;i++)
{
memset(used,0,sizeof(used));
if(dfs(Black[i]))sum++;
//cout<<Black[i]<<endl;
}
cout<<sum<<endl;
}```

## [Codevs] 1014 棋盘染色

1049 棋盘染色 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 有一个5×5的棋盘,上面有一些格子被染成了黑色,其他的格子都是白色,你的任务的对棋盘一些格子进行染色,使得所有的黑色格子能连成一块,并且你染色的格子数目要最少.读入一个初始棋盘的状态,输出最少需要对多少个格子进行染色,才能使得所有的黑色格子都连成一块.(注:连接是指上下左右四个方向,如果两个黑色格子只共有一个点,那么不算连接) 输入描述 Input Descri

## bzoj1057: [ZJOI2007]棋盘制作 [dp][单调栈]

Description 国际象棋是世界上最古老的博弈游戏之一,和中国的围棋.象棋以及日本的将棋同享盛名.据说国际象棋起源 于易经的思想,棋盘是一个8*8大小的黑白相间的方阵,对应八八六十四卦,黑白对应阴阳.而我们的主人公小Q, 正是国际象棋的狂热爱好者.作为一个顶尖高手,他已不满足于普通的棋盘与规则,于是他跟他的好朋友小W决定 将棋盘扩大以适应他们的新规则.小Q找到了一张由N*M个正方形的格子组成的矩形纸片,每个格子被涂有黑白两种 颜色之一.小Q想在这种纸中裁减一部分作为新棋盘,当然,他希望这个

## codevs——1169 传纸条（棋盘DP）

2008年NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题解 查看运行结果 题目描述 Description 小渊和小轩是好朋友也是同班同学,他们在一起总有谈不完的话题.一次素质拓展活动中,班上同学安排做成一个m行n列的矩阵,而小渊和小轩被安排在矩阵对角线的两端,因此,他们就无法直接交谈了.幸运的是,他们可以通过传纸条来进行交流.纸条要经由许多同学传到对方手里,小渊坐在矩阵的左上角,坐标(1,1),小轩坐在矩阵的右下角,坐标(m,