题目
分析
本题算法不难,但有一个小坑。
既然是排成1*K
或者K*1
的队列,那么搜索只需要在一个维度(要么行、要么列)展开。
从每行的开头开始,看连续K
个字符是否都是.
(不是#
)。然后不断右移直到第C-K
列。每列的处理与此类似。核心代码如下:
for (int j = 0; j <= C - K; j++)
{
bool valid = true;
for (int k = 0; k < K; k++)
{
if (court[i][j + k] == '#')
{
valid = false;
break;
}
}
if (valid)
{
total_ways++;
}
}
按照这个算法,有没有发现坑在哪里?
如果K==1
,那么这种按行、按列的算法会将结果翻倍。如果K==1
,其实就无所谓行或者列了。所以,这种情况只要统计有多少空地即可。
答案
思考
(略)