洛谷:P3654:First Step (ファーストステップ)


洛谷:P3654:First Step (ファーストステップ)

Table of Contents

题目

P3654:First Step (ファーストステップ)

分析

本题算法不难,但有一个小坑。

既然是排成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,其实就无所谓行或者列了。所以,这种情况只要统计有多少空地即可。

答案

Solution

思考

(略)

上一篇 下一篇