组合数学 Incomplete chess boards boj1111

Incomplete chess boardsSubmit: 60   Accepted:38Time Limit: 1000MS  Memory Limit: 65536KDescription
Background
Tom gets a riddle from his teacher showing 42 chess boards from each of which two squares are removed. The teacher wants to know which boards can be completely covered by 31 dominoes. He promises ten bars of chocolate for the person who solves the problem correctly. Tom likes chocolate, but he cannot solve this problem on his own. So he asks his older brother John for help. John (who likes chocolate as well) agrees, provided that he will get half the prize.
John's abilities lie more in programming than in thinking and so decides to write a program. Can you help John? Unfortunately you will not win any bars of chocolate, but it might help you win this programming contest.
Problem
You are given are 31 dominoes and a chess board of size 8 * 8, two distinct squares of which are removed from the board. The square in row a and column b is denoted by (a, b) with a, b in {1, . . . , 8}.
A domino of size 2 × 1 can be placed horizontally or vertically onto the chess board, so it can cover either the two squares {(a, b), (a, b + 1)} or {(b, a), (b + 1, a)} with a in {1, . . . , 8} and b in {1, . . . , 7}. The object is to determine if the so-modified chess board can be completely covered by 31 dominoes.
For example, it is possible to cover the board with 31 dominoes if the squares (8, 4) and (2, 5) are removed, as you can see in Figure 1.



Input
The first input line contains the number of scenarios k. Each of the following k lines contains four integers a, b, c, and d, separated by single blanks. These integers in the range {1, . . . , 8} represent the chess board from which the squares (a, b) and (c, d) are removed. You may assume that (a, b) != (c, d).


Output
The output for every scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print the number 1 if the board in this scenario can be completely covered by 31 dominoes, otherwise write a 0. Terminate the output of each scenario with a blank line.


Sample Input

3
8 4 2 5
8 8 1 1
4 4 7 1


Sample Output

Scenario #1:
1

Scenario #2:
0

Scenario #3:
0

题目大意：
从一个8x8的棋盘中挖去两个格子，然后用31个1x2的多米罗牌去覆盖这个棋盘，判断是否能实现。

解法：把残缺的棋盘的格子间隔的涂色，即两个相邻的格子的颜色不同，那么用1*2的格子去铺棋盘，铺得的结果是：铺过的两种颜色的格子数是相等的 (任意相邻的两个格子的颜色不同，铺下一个1*2的格子的时候同时占有各颜色一个)，因此，最后判定去掉的两个格子是否是同色的就可以判定是否可以成功铺 下31个1*2的格子了。（所有的行数和列数相加得奇数的格子的颜色相同(假如是白色)，相加得偶数的格子的颜色也相同（则为黑色））。

这是一个简单的组合数学的问题，但是这种思维还是值得学习的。

#include 
using namespace std;

int squre[9][9];

/*初始化这个棋盘，然相邻的任何两个各自的颜色想异(0和1)*/
void init()
{
    int i, j, fst_color, crt_color;
    fst_color = crt_color = 0;

    for (i=1 ; i<=8 ; i++)
    {
        fst_color ^= 1;
        crt_color = fst_color;
        for (j=1 ; j<=8 ; j++)
        {
            squre[i][j] = crt_color;
            crt_color ^= 1;
        }
    }
}

int main(int argc, char *argv[])
{
    int k, a, b, c, d, i;

    init();
    cin >> k;
    for (i=0 ; i    {
        cin >> a >> b >> c >> d;
        cout << "Scenario #" << i + 1 << ":" << endl;

        /*判断被挖去的这两个格子的颜色是否相同，如果相同就不可能*/
        cout << (squre[a][b] ^ squre[c][d]) << endl;
        cout << endl;
    }
   
}