【题目来源】洛谷AT_abc464_b [ABC464B] Crop - 洛谷【题目描述】There is a black-and-white image of heightH HHpixels and widthW WWpixels. The color of the pixel at thei ii-th row from the top andj jj-th column from the left is given as a characterC i , j C_{i,j}Ci,j​, where.represents white and#represents black.From the top, bottom, left, and right edges of this image, remove rows and columns where all pixels are white. Specifically, perform the following operations in order:While the topmost row of the image is entirely white, repeat removing the topmost row.While the bottommost row of the image is entirely white, repeat removing the bottommost row.While the leftmost column of the image is entirely white, repeat removing the leftmost column.While the rightmost column of the image is entirely white, repeat removing the rightmost column.Output the image after processing.The given image contains at least one black pixel.有一张高度为H HH像素、宽度为W WW像素的黑白图像。从上往下第i ii行、从左往右第j jj列的像素颜色用字符C i , j C_{i,j}Ci,j​表示其中.表示白色#表示黑色。从该图像的上、下、左、右边缘移除所有像素均为白色的行和列。具体按以下顺序执行操作当图像最上面一行全部为白色时重复移除最上面一行。当图像最下面一行全部为白色时重复移除最下面一行。当图像最左面一列全部为白色时重复移除最左面一列。当图像最右面一列全部为白色时重复移除最右面一列。输出处理后的图像。给定的图像中至少包含一个黑色像素。【输入】The input is given from Standard Input in the following format:H HHW WWC 1 , 1 C 1 , 2 … C 1 , W C_{1,1}C_{1,2}\ldots C_{1,W}C1,1​C1,2​…C1,W​C 2 , 1 C 2 , 2 … C 2 , W C_{2,1}C_{2,2}\ldots C_{2,W}C2,1​C2,2​…C2,W​⋮ \vdots⋮C H , 1 C H , 2 … C H , W C_{H,1}C_{H,2}\ldots C_{H,W}CH,1​CH,2​…CH,W​【输出】Output the image after processing in the following format.Here,h hhandw wware the height and width of the image after processing, in pixels, respectively.c i , j c_{i,j}ci,j​is the character representing the color of the pixel at thei ii-th row from the top andj jj-th column from the left;c i , j c_{i,j}ci,j​must be.if the pixel is white and#if it is black.c 1 , 1 c 1 , 2 … c 1 , w c_{1,1}c_{1,2}\ldots c_{1,w}c1,1​c1,2​…c1,w​c 2 , 1 c 2 , 2 … c 2 , w c_{2,1}c_{2,2}\ldots c_{2,w}c2,1​c2,2​…c2,w​⋮ \vdots⋮c h , 1 c h , 2 … c h , w c_{h,1}c_{h,2}\ldots c_{h,w}ch,1​ch,2​…ch,w​【输入样例】4 5 ..... ..#.. .###. .....【输出样例】.#. ###【核心思想】问题分析给定一个H × W H \times WH×W的黑白图像.表示白色#表示黑色需要按顺序从四个边缘上、下、左、右移除所有全白的行或列直到每个边缘遇到第一个非全白的行/列为止。由于保证至少有一个黑色像素最终图像非空。本质上是在二维矩阵中定位包含黑色像素的最小行区间和列区间。算法选择直接模拟按照题目要求的顺序逐边检查并标记全白行/列边界收缩通过四个方向的扫描确定保留区域的上边界t o p toptop、下边界b o t t o m bottombottom、左边界l e f t leftleft、右边界r i g h t rightright关键步骤读取图像读入H HH、W WW和像素矩阵C [ 1.. H ] [ 1.. W ] C[1..H][1..W]C[1..H][1..W]确定上边界t o p toptop从第1 11行开始向下扫描找到第一个不全白的行确定下边界b o t t o m bottombottom从第H HH行开始向上扫描找到第一个不全白的行确定左边界l e f t leftleft从第1 11列开始向右扫描找到第一个不全白的列确定右边界r i g h t rightright从第W WW列开始向左扫描找到第一个不全白的列输出保留区域输出C [ i ] [ j ] C[i][j]C[i][j]其中i ∈ [ t o p , b o t t o m ] i \in [top, bottom]i∈[top,bottom]j ∈ [ l e f t , r i g h t ] j \in [left, right]j∈[left,right]时间/空间复杂度时间复杂度O ( H × W ) O(H \times W)O(H×W)每个像素最多被检查常数次行扫描和列扫描空间复杂度O ( H × W ) O(H \times W)O(H×W)存储原始图像矩阵模拟与边界收缩的核心思想方向独立性四个边缘的移除操作互不影响最终结果因为全白行/列的移除不会使内部的非全白行/列变成全白因此可以直接计算四个边界而不必真的逐行逐列删除最小包围矩形问题等价于找到包含所有黑色像素的最小轴对齐矩形四个边界分别由最上、最下、最左、最右的黑色像素位置决定顺序无关性优化虽然题目规定了上→下→左→右的顺序但由于黑色像素的位置固定实际边界结果与处理顺序无关可独立计算四个边界后统一输出适用于二维矩阵的边缘裁剪、最小包围区域定位等基础图像处理问题【算法标签】#入门 #模拟【代码详解】#includebits/stdc.husingnamespacestd;constintN55;// 最大图像尺寸inth,w;// h: 图像高度, w: 图像宽度chara[N][N];// a[i][j]: 原始图像第i行第j列的像素intb[N][N];// b[i][j]: 标记该像素是否被移除1表示移除0表示保留intmain(){cinhw;// 读入图像高度和宽度// 读入图像for(inti1;ih;i)for(intj1;jw;j)cina[i][j];// 第一步移除顶部全白行 booloktrue;while(ok){// 从上往下检查每一行for(inti1;ih;i){boolflag1;// flag1表示当前行全白// 检查第i行是否全白for(intj1;jw;j){if(a[i][j]#)// 发现黑色像素{flag0;// 不是全白行break;}}if(flag)// 第i行全白标记移除{for(intj1;jw;j)b[i][j]1;// 标记该行为移除}else// 第i行不全白停止检查只移除连续顶部的全白行{okfalse;break;}}}// 第二步移除左侧全白列 oktrue;while(ok){// 从左往右检查每一列for(intj1;jw;j){boolflag1;// flag1表示当前列全白// 检查第j列是否全白for(inti1;ih;i){if(a[i][j]#)// 发现黑色像素{flag0;// 不是全白列break;}}if(flag)// 第j列全白标记移除{for(inti1;ih;i)b[i][j]1;// 标记该列为移除}else// 第j列不全白停止检查{okfalse;break;}}}// 第三步移除底部全白行 oktrue;while(ok){// 从下往上检查每一行for(intih;i1;i--){boolflag1;// flag1表示当前行全白// 检查第i行是否全白for(intj1;jw;j){if(a[i][j]#)// 发现黑色像素{flag0;// 不是全白行break;}}if(flag)// 第i行全白标记移除{for(intj1;jw;j)b[i][j]1;// 标记该行为移除}else// 第i行不全白停止检查{okfalse;break;}}}// 第四步移除右侧全白列 oktrue;while(ok){// 从右往左检查每一列for(intjw;j1;j--){boolflag1;// flag1表示当前列全白// 检查第j列是否全白for(inti1;ih;i){if(a[i][j]#)// 发现黑色像素{flag0;// 不是全白列break;}}if(flag)// 第j列全白标记移除{for(inti1;ih;i)b[i][j]1;// 标记该列为移除}else// 第j列不全白停止检查{okfalse;break;}}}// 输出处理后的图像 for(inti1;ih;i){for(intj1;jw;j){if(!b[i][j])// 只输出未被移除的像素couta[i][j];}coutendl;// 每行结束换行}return0;}【运行结果】4 5 ..... ..#.. .###. ..... .#. ###