前置:递归
最低所需知识点:深度优先搜索
看数据范围很明显的搜索了.
刚开始看见 还以为要什么剪枝 结果依旧蔡老师的一氧化二氢数据.
普通的深度优先搜索即可通过此题.
定义一个 bool 数组记录每一个格子是否占用.
从上到下 从左到右挨个枚举所有的格子(按行来)
枚举每一个格子的状态
1.不以此格为起点摆放骨牌
2.以此格为起点摆放一个骨牌 并且方向朝右(下一次递归可以直接跳过右边的 因为这样摆肯定会占用右边的格子 所以跳过的正确性不变)
3.以此格为起点摆放一个骨牌 并且方向朝下(不可跳过 因为这一行还有其他的格子需要枚举)
注意摆放时需要判断是否越界 如果越界则无法摆放.同样的 如果之前这个格子被占用了 也无法继续摆放其他的骨牌.
最后枚举全部格子枚举完之后 全部都便利一遍 如果格子被占用 则不参与异或.这样的常数虽然很大 但记住我前面说的话 不用优化!就这样.
注意异或开始时 才可以正常得出结果.