讨论/算法和数据结构/有一道算法题求大佬指点一下/
有一道算法题求大佬指点一下

浴室地板需要平铺。 每个图块都是2×1矩形。 但是,地板上的障碍物如排水管,水槽,马桶,浴室和橱柜无法平铺。 假设您在单元格的n×m网格P中获得有关浴室地板布局的信息,其中P [i] [j]表示该单元格中是否没有障碍物(如果没有障碍物,则为true;如果有障碍物,则为false)。 设计一种算法,确定是否可以在不切割任何瓷砖的情况下将地板瓷砖化。
a)描述解决此问题的有效算法。 b)分析时间复杂度
这个应该是动态规划相关问题吧

展开讨论
共 2 个讨论

力扣上有这道题

https://leetcode-cn.com/problems/broken-board-dominoes/

1

把每行的状态用一个数字的bit位来表示,就是状压dp了,不难理解的