棋盘问题总结

我们在研究问题时经常能碰到这一类为题:在某个棋盘上有一种棋子,问最多放下几个棋子。或者有一堆棋子,问你移去最少的棋子数目,使得剩下来的棋子两两不攻击。

先看下面这道题

问题 E: P1035

时间限制: 1 Sec  内存限制: 128 MB
提交: 82  解决: 35
[提交][状态][讨论版]

题目描述

给出一张n*n(n< =100)的国际象棋棋盘,其中被删除了一些点,问可以使用多少1*2的多米诺骨牌进行掩盖。

输入

第一行为n,m(表示有m个删除的格子) 第二行到m+1行为x,y,分别表示删除格子所在的位置 x为第x行 y为第y列

输出

一个数,即最大覆盖格数

样例输入

8 0

样例输出

32

这道题先想的是状压DP(爆搜)后来不会做啦。

其实一个棋子只能和它上下左右4块中的一块拼成一大块,所以我们把每个棋子与其上下左右四个棋子连一条边。连完所有的边后,我们发现要求的就是最多有多少的边(顶点不能重复)想到了什么?二分图匹配。但它不一定是个二分图啊。我们需要证明这一点。一种口糊的方法就是显然一个点仅走奇数次肯定不能回到原点,所以原图中不存在奇数边的环路,就是二分图啦。还有一种比较巧妙和通用的方法就是将棋盘黑白染色,所有黑的只能与白点发生关系,就是显然的二分图了(黑白两个点集)。对于棋子的问题,我们只要在相互冲突的棋子连上一条边,然后简单的证明一下是不是二分图,最后求最大子独立集或最大匹配即可。

#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;
}
时间: 07-19

棋盘问题总结的相关文章

棋盘覆盖问题

棋盘覆盖问题       问题描述: 在一个2^k×2^k个方格组成的棋盘中,若有一个方格与其他方格不同,则称该方格为一特殊方格,且称该棋盘为一个特殊棋盘.显然特殊方格在棋盘上出现的位置有4^k种情形.因而对任何k≥0,有4^k种不同的特殊棋盘.     下图–图(1)中的特殊棋盘是当k=3时16个特殊棋盘中的一个: 图(1) 题目要求在棋盘覆盖问题中,要用下图-图(2)所示的4种不同形态的L型骨牌覆盖一个给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖. 图(2) 题目

Q:opencv棋盘标定总是找不到角点

可能是:1.pattern_size没有设置正确(棋盘图片的内角点数目,指除去棋盘边缘的棋盘角点) 2.黑白格,彩格我试了一下不好用 3.内角点的行列数目设置,一定要大于2

计算机算法设计与分析之棋盘覆盖问题

一.引子 最近又重新上了算法课,现在想来有点汗颜,大学期间已经学习了一个学期,到现在却依然感觉只是把老师讲过的题目弄懂了,并没有学到算法的一些好的分析方法和思路,碰到一个新的问题后往往感觉很棘手,痛定思痛之后觉得还是好好再学习一遍,争取能理解透彻每种算法的思路和核心,同时也劝诫各位同行们做事要脚踏实地,不能应付老师的作业,最后吃亏的还是自己啊. 二.棋盘覆盖问题 在一个由2^k *2^k个方格组成的棋盘中,恰有一个方格与其他方格不同,称该方格为一特殊方格,且称该棋盘 为一特殊棋盘.现有四种L型骨

棋盘的多米诺覆盖:Dimer Lattice Model,Pfaff 多项式,Kasteleyn 定理

这次来介绍计数组合学里面一个经典的问题:Dimer Lattice Model.问题是这样的:一个有 64 个方格的国际象棋棋盘,有多少种不同的多米诺骨牌覆盖?这里的覆盖是指不重复不遗漏地盖住整个棋盘. 下图是一种可能的覆盖方式(图片来自 Wiki 百科): 这个问题的答案是 12988816,非常大的一个数字,绝对不是一个一个数出来的.1961 年德国物理学家 Kasteleyn 借助于线性代数中的一个结论首先解决了这个问题,我们接下来就介绍他的方法. ~~~~~~~~~~~~~~~~~~~~

nyoj 45 棋盘覆盖

棋盘覆盖 时间限制:3000 ms  |  内存限制:65535 KB 难度:3 描述 在一个2k×2k(1<=k<=100)的棋盘中恰有一方格被覆盖,如图1(k=2时),现用一缺角的2×2方格(图2为其中缺右下角的一个),去覆盖2k×2k未被覆盖过的方格,求需要类似图2方格总的个数s.如k=1时,s=1;k=2时,s=5 输入 第一行m表示有m组测试数据: 每一组测试数据的第一行有一个整数数k; 输出 输出所需个数s; 样例输入 3 1 2 3 样例输出 1 5 21 /* 注意寻找图中规律

棋盘问题 POJ - 1321

在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别.要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放k个棋子的所有可行的摆放方案C. Input 输入含有多组测试数据. 每组数据的第一行是两个正整数,n k,用一个空格隔开,表示了将在一个n*n的矩阵内描述棋盘,以及摆放棋子的数目. n <= 8 , k <= n 当为-1 -1时表示输入结束. 随后的n行描述了棋盘的形状:每行有n个字符,其中 # 表示棋盘区域, . 表示空白

[ZJOI2007]棋盘制作

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

[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,