精华内容
下载资源
问答
  • 理解:只有(x1+y1)与(x2+y2)一基一偶就可以完美覆盖,同基同偶都是NO。 #include #include using namespace std; int main() { int t,a,b,c,d,m,n; cin >> t; for (int i=1;i { scanf("%d%d",&m...

    理解:只有(x1+y1)与(x2+y2)一基一偶就可以完美覆盖,同基同偶都是NO。



    #include <cstdio>

    #include <iostream>
    using namespace std;
    int main()
    {
    int t,a,b,c,d,m,n;
    cin >> t;
    for (int i=1;i<=t;i++)
    {
    scanf("%d%d",&m,&n);
    if (!(m&1)||!(n&1))
    {
    scanf("%d%d%d%d",&a,&b,&c,&d);
    if (!((a+b+c+d)&1))
    printf("NO\n");
    else
    printf("YES\n");
    }
    else
    printf("NO\n");
    }
    return 0;
    }
    展开全文
  • 棋盘覆盖

    2018-03-29 17:33:49
    显然特殊方格在棋盘上出现的位置有4的k次方种,要用以下四种L行的方块将其完全覆盖,且不得有方块重复覆盖解题思路: 分析:此题可以用分治策略进行算法设计,当k&gt;0时,我们可以将2^k-1*2^k-1 棋盘分割成2^...

    棋盘覆盖

    问题描述

    1. 在一个2^k×2^k 个方格组成的棋盘中,恰有一个方格与其他方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。显然特殊方格在棋盘上出现的位置有4的k次方种,要用以下四种L行的方块将其完全覆盖,且不得有方块重复覆盖

    解题思路: 

    分析:此题可以用分治策略进行算法设计,当k>0时,我们可以将

    2^k-1*2^k-1 棋盘分割成2^k×2^k 的子棋盘,特殊方格每次位于4个较小棋盘之一,而且我们可以发现,在无特殊方格的子棋盘中,中心点的临近方格就是L行骨牌的汇合处,即无特殊方格的子棋盘的中心点汇合处,就是L行的骨牌所在位置,所以我们可以每次判断特殊方块的位置,并将无特殊方块的子棋盘的父棋盘中心点汇合处标上,在进行下一次分割,直至棋盘无法分割

    实现:

    #include<stdio.h>
    #include<string.h>
    int title=1;
    int Border[100][100];
    void ChessBoard(int tr,int tc,int dr,int dc,int sizet);
    
    void print(){
    	printf("****************************\n");
    	for(int i=0;i<4;i++){
    		for(int j=0;j<4;j++){
    			printf("%d  ",Border[i][j]);
    		}
    		printf("\n");
    	}
    	printf("\n**********************\n");
    } 
    int main(){
    	memset(Border,0,sizeof(Border));
    	Border[0][1]=0;
    	ChessBoard(0,0,0,1,4);
    	print();
    }
    
    
    void ChessBoard(int tr,int tc,int dr,int dc,int size){
    	if(size==1)  return ;//棋盘无法分割
    	int t= title++;//用于在当前中心点会和处标记L形骨牌
    	int s=size/2;//下一次分割的规模
    	
    	//判断特殊方格是否在左上子棋盘中
    	if(dr<tr+s&&dc<tc+s){
    		//如果特殊方格在此子棋盘中,继续分割; 
    		ChessBoard(tr,tc,dr,dc,s);
    		print();
    	}else{
    		//无特殊方格,将右下角标为特殊方格 ,即为L形骨牌的三分之一 
    		Border[tr+s-1][tc+s-1]=t;
    		ChessBoard(tr,tc,tr+s-1,tc+s-1,s);print();
    	} 
    	
    	//判断特殊方格是否在 左下角的子棋盘中 
    	if(dr>=tr+s&&dc<tc+s){
    		//特殊方格在此子棋盘中 ,继续分割
    		ChessBoard(tr+s,tc,dr,dc,s); print();
    	} else{
    		//无特殊方格,将右上角标为特殊方格 , 即为L形骨牌的三分之一
    		Border[tr+s][tc+s-1]=t;
    		ChessBoard(tr+s,tc,tr+s,tc+s-1,s);print();
    		
    	}
    	
    	//右上角
    	if(dr<tr+s&&dc>=tc+s){
    		ChessBoard(tr,tc+s,dr,dc,s);print();
    	}else{
    		Border[tr+s-1][tc+s]=t;
    		ChessBoard(tr,tc+s,tr+s-1,tc+s,s);print();
    	}
    	//右下角 
    	if(dr>=tr+s&&dc>=tc+s){
    		
    		ChessBoard(tr+s,tc+s,dr,dc,s);print();
    	}else{
    		Border[tr+s][tc+s]=t;
    		ChessBoard(tr+s,tc+s,tr+s,tc+s,s);print();
    	}
    } 
    这里我用print()将标记过程动态化
    
    

    tr:棋盘左上角行号

    tc:期盼左上角列号

    dr:特殊方格行号

    dc:特殊方格列号

    size:棋盘规格

    title:全局变量,用来标识L形骨牌

    border[][]:棋盘


    这里请大家注意对方格进行数字的表示,

    Border[tr+s][tc+s-1]=t;


    这里是最后的结果显示,代码已经亲测过

    展开全文
  • 残缺棋盘覆盖问题

    2019-09-20 20:00:10
     在一个有2N×2N个方格组成的棋盘中,有一个方格残缺(残缺方格位置随机),要求用如下①~④的三格板完全覆盖棋盘中为残缺的方格。    ① ② ③ ④ 例如:  下面是一个4×4的棋盘,其中黑色的...

    残缺棋盘的覆盖问题

    问题描述:

      在一个有2×2N个方格组成的棋盘中,有一个方格残缺(残缺方格位置随机),要求用如下①~④的三格板完全覆盖棋盘中为残缺的方格。

                              

                ①            ②            ③            ④

     

    例如:

      下面是一个4×4的棋盘,其中黑色的方格代表残缺的方格。

                            

      使用三格板覆盖后如下图,其中相同的数字表示同一块三格板。               

     

                            

     

     

     分析: 

     1×1         2×2                   4×4                      8×8

     

       当棋盘大小为1×1时,棋盘残缺,不需要三格板覆盖;当棋盘大小为2×2时,有一个方格残缺,用一个三格板正好能完全覆盖;当棋盘越来越大时,覆盖棋盘的方式便较难确定。但是棋盘较小时,问题就比较容易解决了,所以可以采用分治法来解决。

     

                         

      上图是一个4×4的残缺棋盘,我们可以将这个4×4的棋盘分成4个2×2的棋盘, 其中有一个2×2的棋盘存在残缺方格,剩下三个则没有残缺方格。但是只有当棋盘中存在一个残缺方格是,棋盘才能用三格板完全覆盖,所以我们可以为那三个没有残缺方格的棋盘加一个残缺方格,残缺方格不能随便加,下图中灰色的方块便是加的残缺方块,加的三个残缺方块必要能组成一个三格板才行。

     

                              

     

     

     代码:

     

     

    #include <iostream>
    #include<iomanip>
    using namespace std;
    
    const int MAXSIZE = 100;
    int tile = 1;
    int board[MAXSIZE][MAXSIZE];
    
    void chessBoard(int tr, int tc, int dr, int dc, int size)
    {
        if(size == 1)
            return;
        int t = tile++;
        int s = size / 2;
        //覆盖左上角棋盘
        if(dr < tr + s && dc < tc + s)
        {//残缺方格在左上角
            chessBoard(tr, tc, dr, dc, s);
        }
        else
        {//此部分无残缺方格,将右下角方格当成残缺方格
            board[tr + s - 1][tc + s - 1] = t;
            chessBoard(tr, tc, tr + s - 1, tc + s - 1, s);
        }
    
        //覆盖右上角棋盘
        if (dr < tr + s && dc >= tc + s)
        {//残缺方格在右上角
            chessBoard(tr, tc + s, dr, dc, s);
        }
        else
        {//此部分无残缺方格,将左下角方格当成残缺方格
            board[tr + s -1][tc + s] = t;
            chessBoard(tr, tc + s, tr + s - 1, tc + s, s);
        }
    
        //覆盖左下角棋盘
        if (dr >= tr + s && dc < tc + s)
        {//残缺方格在左下角
            chessBoard(tr + s, tc, dr, dc, s);
        }
        else
        {//此部分无残缺方格,将右上角方格当成残缺方格
            board[tr + s][tc + s - 1] = t;
            chessBoard(tr + s, tc, tr + s, tc + s -1, s);
        }
    
        //覆盖右下角棋盘
        if (dr >= tr + s && dc >= tc + s)
        {//残缺方格在右下角
            chessBoard(tr + s, tc + s, dr, dc, s);
        }
        else
        {//此部分无残缺方格,将左上角方格当成残缺方格
            board[tr + s][tc + s] = t;
            chessBoard(tr + s, tc + s, tr +s, tc + s, s);
        }
    }
    int main()
    {
        int size;
        cin>>size;
        int dr, dc;
        cin >> dr >> dc;
        chessBoard(0, 0, dr, dc, size);
        for (int i = 0; i < size; i++)
        {
            for (int j = 0; j < size; j++)
                cout << setw(5) << setiosflags(ios::left) << board[i][j];
            cout << endl;
        }
        return 0;
    }

     

     输入:

    8

    1 1

    输出:

    3    3    4    4    8    8    9    9
    3    0    2    4    8    7    7    9
    5    2    2    6   10 10    7   11
    5    5    6    6    1  10   11   11
    13 13  14   1    1  18   19   19
    13 12  14  14  18 18   17   19
    15 12  12  16   20 17  17    21
    15 15  16  16   20 20   21   21

     

    转载于:https://www.cnblogs.com/yichenxing/p/11077053.html

    展开全文
  • 完全覆盖

    2017-02-25 11:09:43
    描述 有一天小董子在玩一种游戏----用2*1或1*2的骨牌把m*n的棋盘完全覆盖。但他感觉游戏过于简单,于是就随机生成了两个方块的位置(可能相同),标记一下,标记后的方块不用覆盖。还要注意小董子只有在m*n的棋盘能...

    完全覆盖

    时间限制:2000 ms  |  内存限制:65535 KB
    难度:3
    描述
    有一天小董子在玩一种游戏----用2*1或1*2的骨牌把m*n的棋盘完全覆盖。但他感觉游戏过于简单,于是就随机生成了两个方块的位置(可能相同),标记一下,标记后的方块不用覆盖。还要注意小董子只有在m*n的棋盘能被完全覆盖后才会进行标记。现在他想知道:如果标记前m*n的棋盘能被完全覆盖,标记后的棋盘是否能被完全覆盖?
    输入
    第一行有一个整数t(1<=t<=100000),表示有t组测试数据。
    每组测试数据有三行或一行。
    第一行有两个整数 m,n(1<=m,n<=25535)表示行数和列数。
    如果需要标记的话,第二、三行都有两个整数 a,b(1<=a<=m,1<=b<=n),表示行标和列标。
    输出
    若标记前m*n的棋盘能被完全覆盖,则看标记后的棋盘是否能被完全覆盖,能则输出“YES”,否则输出“NO”;若标记前m*n的棋盘不能被完全覆盖则输出“NO”。
    样例输入
    2
    4 4
    1 1
    4 4
    5 5
    
    样例输出
    NO
    NO
    //标记前只要格子总数为偶数即可, 标记后变成不规则区域两点间横纵坐标之差必须一奇一偶才可完全覆盖 
    #include<stdio.h>
    #include<iostream>
    #include<math.h>
    using namespace std;
    int abs(int a)
    {
        if(a<0)
        {
          a=-a;
        }
        return a;
    }
    int main()
    {
        int t;
        scanf("%d",&t);
        while(t--)
        {
            int n,m;
            scanf("%d%d",&n,&m);
            if((n*m)%2==0)
            {
                int x,y,x1,y1;
                scanf("%d%d%d%d",&x,&y,&x1,&y1);
                if(abs(x1-x)%2==1&&abs(y1-y)%2==1||abs(x1-x)%2==0&&abs(y1-y)%2==0)
                {
                    printf("NO\n");
                }
                else
                    printf("YES\n");
            }
            else
                printf("NO\n");
        }
    }
    

    展开全文
  • 完全覆盖问题

    千次阅读 2017-07-09 17:21:58
    描述 有一天小董子在玩一种游戏----用2*1或1*2的骨牌把m*n的棋盘完全覆盖。但他感觉游戏过于简单,于是就随机生成了两个方块的位置(可能相同),标记一下,标记后的方块不用覆盖。还要注意小董子只有在m*n的棋盘能...
  • 棋盘覆盖算法

    千次阅读 2016-10-27 20:24:06
    棋盘覆盖中我们有四种L型骨牌,要求是使用这些骨牌,覆盖完全棋盘上除特殊位置以外的所有位置,并且任何两个L型骨牌不得重叠覆盖。 在任何一个(2^k)*(2^k)的棋盘覆盖中,用到的L型骨牌个数恰为(4^k-1)/3。思路...
  • nyoj 328 完全覆盖

    2018-04-21 14:25:51
    完全覆盖时间限制:2000 ms | 内存限制:65535 KB难度:3描述有一天小董子在玩一种游戏----用2*1或1*2的骨牌把m*n的棋盘完全覆盖。但他感觉游戏过于简单,于是就随机生成了两个方块的位置(可能相同),标记一下...
  • nyoj328 完全覆盖

    2019-10-05 15:13:34
    描述有一天小董子在玩一种游戏----用2*1或1*2的骨牌把m*n的棋盘完全覆盖。但他感觉游戏过于简单,于是就随机生成了两个方块的位置(可能相同),标记一下,标记后的方块不用覆盖。还要注意小董子只有在m*n的棋盘能被...
  • nyoj 515完全覆盖 II

    2018-04-21 14:28:25
    完全覆盖 II时间限制:1000 ms | 内存限制:65535 KB难度:4描述有一天acmj在玩一种游戏----用2*1或1*2的骨牌把m*n的棋盘完全覆盖。但他感觉把棋盘完全覆盖有点简单,他想能不能把完全覆盖的种数求出来?由于游戏...
  • 完全覆盖1-OJ

    2017-07-09 12:28:43
    有一天小董子在玩一种游戏----用2*1或1*2的骨牌把m*n的棋盘完全覆盖。但他感觉游戏过于简单,于是就随机生成了两个方块的位置(可能相同),标记一下,标记后的方块不用覆盖。还要注意小董子只有在m*n的棋盘能被完全...
  • 描述 有一天acmj在玩一种游戏----用2*1或1*2的骨牌把m*n的棋盘完全覆盖。但他感觉把棋盘完全覆盖有点简单,他想能不能把完全覆盖的种数求出来?由于游戏难度增加他自己已经没法解决了,于是他希望大家能用程序来帮他...
  • 有一天小董子在玩一种游戏----用2*1或1*2的骨牌把m*n的棋盘完全覆盖。但他感觉游戏过于简单,于是就随机生成了两个方块的位置(可能相同),标记一下,标记后的方块不用覆盖。还要注意小董子只有在m*n的棋盘能被完全...
  • 2k*2k 棋盘覆盖问题

    千次阅读 2020-04-25 20:04:01
    棋盘覆盖问题 问题叙述 在一个2k×2k个方格组成的棋盘中,恰有一个方格与其它方格不同,称该方格为一特殊方格,且...关注的重点是特殊方格,2k2k的棋盘上如果没有特殊点,那么L型骨牌不可能完全覆盖,那么我们分治...
  • 有一天小董子在玩一种游戏----用21或12的骨牌把mn的棋盘完全覆盖。但他感觉游戏过于简单,于是就随机生成了两个方块的位置(可能相同),标记一下,标记后的方块不用覆盖。还要注意小董子只有在mn的棋盘能被完全覆盖...
  • 有一天acmj在玩一种游戏----用2*1或1*2的骨牌把m*n的棋盘完全覆盖。但他感觉把棋盘完全覆盖有点简单,他想能不能把完全覆盖的种数求出来?由于游戏难度增加他自己已经没法解决了,于是他希望大家能用程序来帮他把...
  • 分治-棋盘覆盖问题

    2016-04-16 21:07:19
    在一个2^k*2^k个方格组成的棋盘中,任意存在一个特殊方格,那么总有(4^k-1)/3个L型骨牌可以将剩余方格完全覆盖。 分析: 将棋盘横竖四等分,则特殊方格必存在于某一区域。存在特殊方格的区域自然可以完全覆盖,...
  • 分治法实现棋盘的“3-L形”完全覆盖,java实现。
  • NYOJ 515 完全覆盖 II (状态压缩dp)

    千次阅读 2016-06-10 18:03:29
    描述有一天acmj在玩一种游戏----用2*1或1*2的骨牌把m*n的棋盘完全覆盖。但他感觉把棋盘完全覆盖有点简单,他想能不能把完全覆盖的种数求出来?由于游戏难度增加他自己已经没法解决了,于是他希望大家能用程序来帮他...
  • 描述有一天小董子在玩一种游戏----用2*1或1*2的骨牌把m*n的棋盘完全覆盖。但他感觉游戏过于简单,于是就随机生成了两个方块的位置(可能相同),标记一下,标记后的方块不用覆盖。还要注意小董子只有在m*n的棋盘能被...
  • U91193 棋盘覆盖 ▲ 有个重要的思想:为了达成分治的目的,要在没有真正特殊点的子棋盘内假设一个特殊点,以此出发才能继续分治 ▲ 此外,注意到在不同层函数(即不同大小的棋盘)之间,L型块编号应是递增的,但在同...
  • =10^9,用1*2 的骨牌(可横放或竖放)完全覆盖,骨牌不能重叠,有多少种不同的覆盖的方法。你只需要求出覆盖方法总数 mod p 的值即可。 看到1e9立马知道快速幂DP或者数学方法,然后m&lt;=5就状压吧 定义f[s][t]...
  • 一张8行8列的棋盘一共有64个方格,用一些形状相同的多米诺骨牌覆盖,每一张覆盖相邻的两个方格,没有相互重叠,能用32张这样的多米诺骨牌完全覆盖整张棋盘称为多米诺骨牌完美覆盖或者盖瓦。这样的完美覆盖是存在的,...
  • 8*8的棋盘被扣掉两个,问还能用2*1的瓷砖完全覆盖不? 【解题思路】 就是把棋盘染色成国际象棋黑白相间的棋盘,如果两个格子同色则不可,否则可以。 if (((a + b) & 1) == ((c + d) & 1))同奇偶,不行
  • 问题一:棋盘覆盖问题  对于一个规模为的棋盘,其中有一个方格和其他方格完全不同,称这一方格为特殊方格,且称该棋盘为特殊棋盘,设计一种算法可以使用4种不同的L型骨牌来填充棋牌。 解答:采用分治策略。 第...
  • 全面覆盖

    2017-07-10 11:27:34
    描述有一天小董子在玩一种游戏----用2*1或1*2的骨牌把m*n的棋盘完全覆盖。但他感觉游戏过于简单,于是就随机生成了两个方块的位置(可能相同),标记一下,标记后的方块不用覆盖。还要注意小董子只有在m*n的棋盘能被...

空空如也

空空如也

1 2 3 4 5
收藏数 97
精华内容 38
关键字:

棋盘完全覆盖