礼物

题目

值得纪念的日子总是需要一点或多或少的礼物。

小R的生日就在下一周了，小J想要给小R送一个礼物，他在橙色软件翻了许久，最终决定送一副拼图给小R。

拿到拼图后，小J想要把他拼好再送给小R，不过看着满桌的拼图碎片小J陷入了沉思，小J想知道他手上的这块拼图碎片可以放在多少个地方。

小J现在有一个 10×10 的拼图棋盘，其中为1的格子代表这里已经有拼图了，为0的格子表示还没有拼图。同时小J手上还有一片拼图，这片拼图的形状可以在一个小棋盘中用一个完整的连通块表示，在这个小棋盘中为1的格子表示这片拼图的形状，所有1所在的方块能够构成一个完整的联通块。他想知道这片拼图在整个棋盘中有多少个位置可以放下，注意该拼图具有方向性，不可在棋盘中进行旋转。

输入：共19行。第1-15行，每行10个整数，表示拼图棋盘，整数仅可能出现0或1。第16-19行，每行4个整数，表示需要被放入棋盘的拼图，整数仅可能出现0或1，所有为1的格子共同构成了拼图的形状。
输出：1个整数，表示有多少个位置可以放下这片拼图。

提示：对于50%的数据，最多存在一个位置可以放下拼图。对于100%的数据，存在多个位置可以放下该拼图。

样例1：

1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 0 0 0 0 1 1 1 1
1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
0 0 0 0
0 1 1 1
0 0 1 0
0 0 0 0

1

第7行连续3个空格子和第8行1个独立空格子共同构成能放下该拼图的空间，故存在1个位置。

样例2：

1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 1 1 1 1 1
1 0 0 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
0 0 0 0
0 1 1 1
0 0 1 0
0 0 0 0

3

第7行每连续3个空格子和第8行对应空格子共构成3个可放位置。

思路

枚举拼图左上角放在棋盘的每个位置 (i, j)，范围 i ∈ [0, 11]、j ∈ [0, 6]（棋盘15×10，拼图4×4，避免越界）。对每个位置，用双重循环遍历拼图的4×4区域：若拼图某格为1，则检查对应棋盘格 board[i+d][j+e] 是否为0；若不为0，立即将 fit 标记为 false 并双重 break 跳出。检查完后若 fit 仍为 true，则计数加一。

#include<bits/stdc++.h>
using namespace std;

int main(){
    int board[15][10];
    int piece[4][4];

    for(int c1=0;c1<15;c1++)
        for(int c2=0;c2<10;c2++)
            cin>>board[c1][c2];

    for(int c1=0;c1<4;c1++)
        for(int c2=0;c2<4;c2++)
            cin>>piece[c1][c2];

    int ans=0;

    for(int c1=0;c1<12;c1++){
        for(int c2=0;c2<7;c2++){
            bool fit=true;
            for(int d=0;d<4;d++){
                for(int e=0;e<4;e++){
                    if(piece[d][e]==1){
                        if(board[c1+d][c2+e]!=0){
                            fit=false;
                            break;
                        }
                    }
                }
                if(!fit) break;
            }
            if(fit) ans++;
        }
    }

    cout<<ans<<endl;
    return 0;
}

复杂度分析

• 时间复杂度：O(12 × 7 × 4 × 4) = O(1)，数据规模固定，常数次枚举。
• 空间复杂度：O(1)，两个固定大小的二维数组。

← 返回菜鸟的coding