Description

题目传送门：P7012 [CERC2013] Draughts。

简单回溯题目，你操作白棋，判断白棋最多能吃几个敌方的棋。

Analysis

考虑 $n\le10$，直接爆搜（回溯）。

分类讨论：

  • 字符 $\tt #$ 和 $\tt .$ 表示空的黑色和白色方块，$\tt W$ 表示有浅色棋子的方块，$\tt B$ 表示有深色棋子的方块。

  • 增量数组：

    1
    2
    const int dx[4] = {-2,-2,2,2};
    const int dy[4] = {-2,2,2,-2};

  • 多组测试数据记得复原。

  • 记得回溯。

  • 找到每一个浅色棋子，去看它旁边有没有深色棋子。

  • 记得找最大值，没有白棋输出 $-1$。

时间复杂度 $\mathcal{O}(n^2)$。