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

题目

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

答案

思考

这个暴力解法的复杂度会来到\(O(R*C*K)\)，有没有更快的方法呢？

其实，如果在一个长度为K的序列中出现了#（障碍），那么从这个障碍位置下一个开始的位置才可能是我们放下队伍的位置。

有一种方法是滑动窗口法。先统计初始窗口（以某一行为例，就是0-(K-1））中的障碍，如果为0，自然就是一个放置方案。然后不断向右滑动，并更新障碍数量：

1. 原来最左的（j-k）会出去。如果它是障碍，障碍数减1。
2. 加入新来的最右（j）。如果它是障碍，障碍数加1。
3. 最后统计这个新区间障碍总数，如果是0，自然也是一种放置的方法。

核心代码如下：¹

int countRowPlace(vector<vector<char>> court, int R, int C, int K)
{
    int c = 0;
    for (int i = 0; i < R; i++)
    {
        // Count blocked cells in first window
        int blocked = 0;
        for (int k = 0; k < K; k++)
        {
            if (court[i][k] == B)
                blocked++;
        }
        if (blocked == 0)
            c++;

        // Slide the window
        for (int j = K; j < C; j++)
        {
            // Remove leftmost cell from window
            if (court[i][j - K] == B)
                blocked--;
            // Add new rightmost cell to window
            if (court[i][j] == B)
                blocked++;

            if (blocked == 0)
                c++;
        }
    }

    return c;
}

这个方法可以将时间复杂度降低到\(O(R*C)\)。