剪纸游戏【牛客tracker 每日一题】
剪纸游戏
时间限制：3秒 空间限制：256M
知识点：广度优先搜索(BFS)
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
小蓝拿着一张n × m n×mn×m的方格纸从中剪下若干不相连的图案；剪裁时只会沿着方格网线裁切，因此不会破坏任何一个完整的小方格。
小灰灰只拿到了剩余的残缺纸张。若用'.'表示被剪去的小方格，'*'表示仍保留的小方格，则他得到一张由'.'与'*'组成的矩阵。由于各个剪下的图案之间互不连通，小灰灰可以根据'.'的连通块反推出每一个被剪下来的图案。
现在小灰灰想知道：在所有被剪下来的图案中，有多少个是长方形（正方形视为特殊的长方形）。
输入描述：
第一行输入两个整数n , m ( 1 ≦ n , m ≦ 1000 ) n,m(1≦n,m≦1000)n,m(1≦n,m≦1000)——纸张的行数与列数。
接下来n nn行，每行输入一个长度为m mm的由'.'与'*'组成的字符串，描述残缺纸张的形状：
'.'代表该方格已被剪去；'*'代表该方格仍保留。
输出描述：
输出一个整数，表示被剪下来的图案中长方形的数量。
示例1
输入：
4 10 *.*.*...** ...***.*.. .**..*.*.. *..*****..输出：
4说明：
可以看出，图中恰有一个正方形，三个长方形，共计四个长方形。
解题思路
本题核心是BFS连通块遍历+外接矩形验证，高效统计符合要求的长方形图案数量。题目要求统计被剪去的'.'连通块中为标准长方形（含正方形）的数量，首先遍历整个网格，对未访问的'.'执行B F S BFSBFS，遍历过程中记录该连通块的最小/最大行、列坐标，确定其最小外接矩形。随后验证该外接矩形内的所有格子是否均为'.'，若完全匹配则说明该连通块是长方形，计数加一；否则判定为非法。通过标记已访问的格子避免重复遍历，整体时间复杂度为O ( n m ) O(nm)O(nm)，完美适配n , m ≤ 1000 n,m≤1000n,m≤1000的大数据规模。
总结
核心逻辑：用B F S BFSBFS找到所有'.'连通块，验证其外接矩形是否完全由自身填充，统计长方形数量。
关键操作：B F S BFSBFS遍历连通块、记录边界坐标、矩形全覆盖校验、访问标记去重。
效率保障：线性时间复杂度，无冗余计算，高效处理千万级网格数据。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;ll n,m;charmp[N][N];ll a[N][N];ll dir[][2]={{1,0},{-1,0},{0,-1},{0,1}};llbfs(ll x,ll y){queue<pll>q;q.push({x,y});ll x1=INT_MAX,x2=0,y1=INT_MAX,y2=0;x1=min(x1,x);x2=max(x2,x);y1=min(y1,y);y2=max(y2,y);while(!q.empty()){ll dx=q.front().first;ll dy=q.front().second;q.pop();for(ll i=0;i<4;i++){ll ex=dx+dir[i][0];ll ey=dy+dir[i][1];if(ex<1||ex>n||ey<1||ey>m||mp[ex][ey]=='*'||mp[ex][ey]=='-'){continue;}x1=min(x1,ex);x2=max(x2,ex);y1=min(y1,ey);y2=max(y2,ey);mp[ex][ey]='-';q.push({ex,ey});}}for(ll i=x1;i<=x2;i++){for(ll j=y1;j<=y2;j++){if(mp[i][j]=='*'){return0;}}}return1;}intmain(){cin>>n>>m;for(ll i=1;i<=n;i++){for(ll j=1;j<=m;j++){cin>>mp[i][j];}}ll sum=0;for(ll i=1;i<=n;i++){for(ll j=1;j<=m;j++){if(mp[i][j]=='.')sum+=bfs(i,j);}}cout<<sum<<endl;return0;}