标签:dfs

2 篇文章

CF293B Distinct Paths 题解
题意 给定一个$n\times m$的矩形色板,有kk种不同的颜料,有些格子已经填上了某种颜色,现在需要将其他格子也填上颜色,使得从左上角到右下角的任意路径经过的格子都不会出现两种及以上相同的颜色。路径只能沿着相邻的格子,且只能向下或者向右。 计算所有可能的方案,结果对 $1000000007 (10^9 + 7)$ 输入及输出格式 输入格式 第一…
洛谷P1331 海战 题解
题目传送门 思路 肯定食用dfs啦。。。 但关键是两条船接触了怎么判断呢?? 上图: 可以发现一下规律 当两条船接触时,必有一条直线连续穿过两条船 当一条船不与另一条船接触时,没有一条直线连续穿过两条船 所以只需要在每一次碰见一条船的一部分(一条船内每个点都要拓展一遍)时,将其沿右上、左下分别拓展一遍,边拓展边用sum前缀和check一遍就好啦。。…