Description

题目传送门：P10313 [SHUPC 2024] 占地斗士！。

简单搜索题。

Analysis

容易发现，$1\le n,m\le10$，地图很小，所以考虑 DFS 算法。

其实是回溯，不是深度优先搜索。

题目不难，但细节多。

  • 用变量存下已经放置的卡牌数量。
  • 用 $\mathcal{vis}$ 记录此卡牌是否放置过（不能直接改地图，这是回溯的重要部分）。
  • 其它就是回溯+剪枝即可。

一些细节：

  • 暴力枚举每个形状可以放的所有位置。
  • 是 # 不能放，换个位置。
  • 可以放的话，卡牌数自增，答案加上占地格子数，不是 $1$。
  • 可以放，记得 $vis$ 标记位置。

若所有的卡牌都可以放入，那么直接输出 $18$，不用搜了，搜了小心 $\tt TLE$，程序卡死。

都可以放入的数据如下：

输入

1
2
3
4
5
6
7
8
9
10
11
>10 10
>. . . . . . . . . .
>. . . . . . . . . .
>. . . . . . . . . .
>. . . . . . . . . .
>. . . . . . . . . .
>. . . . . . . . . .
>. . . . . . . . . .
>. . . . . . . . . .
>. . . . . . . . . .
>. . . . . . . . . .

输出

1
>18

代码模拟即可。