剪纸游戏时间限制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遍历连通块、记录边界坐标、矩形全覆盖校验、访问标记去重。效率保障线性时间复杂度无冗余计算高效处理千万级网格数据。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;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){queuepllq;q.push({x,y});ll x1INT_MAX,x20,y1INT_MAX,y20;x1min(x1,x);x2max(x2,x);y1min(y1,y);y2max(y2,y);while(!q.empty()){ll dxq.front().first;ll dyq.front().second;q.pop();for(ll i0;i4;i){ll exdxdir[i][0];ll eydydir[i][1];if(ex1||exn||ey1||eym||mp[ex][ey]*||mp[ex][ey]-){continue;}x1min(x1,ex);x2max(x2,ex);y1min(y1,ey);y2max(y2,ey);mp[ex][ey]-;q.push({ex,ey});}}for(ll ix1;ix2;i){for(ll jy1;jy2;j){if(mp[i][j]*){return0;}}}return1;}intmain(){cinnm;for(ll i1;in;i){for(ll j1;jm;j){cinmp[i][j];}}ll sum0;for(ll i1;in;i){for(ll j1;jm;j){if(mp[i][j].)sumbfs(i,j);}}coutsumendl;return0;}