题目描述数字化的海底照片由L×CL \times CL×C的网格表示每个格子为小写字母或点号.。字母表示该位置被某动物的身体占据相同字母且四连通的区域属于同一个动物。不同动物的形状不同规则如下单格子沙丁鱼sardines\texttt{sardines}sardines。宽111长222的矩形鲭鱼mackerels\texttt{mackerels}mackerels。宽111长大于222的矩形鲑鱼salmons\texttt{salmons}salmons。宽等于高且大于111的矩形海龟turtles\texttt{turtles}turtles。宽222长大于222的矩形石斑鱼groupers\texttt{groupers}groupers。宽333长大于333的矩形海豚dolphins\texttt{dolphins}dolphins。宽444长大于444的矩形鲸鱼whales\texttt{whales}whales。宽333长大于333但面积不等于矩形面积的鲨鱼sharks\texttt{sharks}sharks。输入保证不存在其他形状。要求统计每种动物的数量并输出。输入格式第一行为测试用例个数随后有一个空行。每个测试用例第一行为两个整数LLL和CCC均≤64\le 64≤64。随后LLL行每行CCC个字符为小写字母或点号。各测试用例之间有一个空行。输出格式对于每个测试用例输出一行包含888个整数依次为沙丁鱼、鲭鱼、鲑鱼、石斑鱼、海龟、海豚、鲸鱼、鲨鱼的数量用空格分隔。不同测试用例输出之间用一个空行分隔。题目分析每种动物是一个连通块由四方向相邻的同字母格子组成。由于不同动物使用不同字母且字母唯一标识一个动物因此只需对每个连通块进行处理。利用Flood Fill\texttt{Flood Fill}Flood Fill获取该块的所有格子同时记录最小行、最大行、最小列、最大列得到包围矩形的宽度wmax⁡(行差,列差)1w \max(\text{行差}, \text{列差}) 1wmax(行差,列差)1高度hmin⁡(行差,列差)1h \min(\text{行差}, \text{列差}) 1hmin(行差,列差)1此处约定w≤hw \le hw≤h即短边为宽长边为高。若面积等于w×hw \times hw×h则为规则矩形否则为鲨鱼。然后根据(w,h)(w, h)(w,h)的值进行分类。解题思路步骤1\texttt{1}1. 初始化统计变量为000。步骤2\texttt{2}2. 遍历网格每个格子若为字母且未处理则启动Flood Fill\texttt{Flood Fill}Flood Fill。在填充过程中维护全局变量leftC,rightC,topL,bottomL最左、最右、最上、最下列/行和area格子数。步骤3\texttt{3}3. 填充完毕后计算宽度width bottomL - topL 1高度height rightC - leftC 1。若width height则交换使width为短边height为长边。步骤4\texttt{4}4. 比较area与width * height若不等则为鲨鱼sharks。否则按下列顺序分类width 1 height 1沙丁鱼。width 1 height 2鲭鱼。width 1 height 2鲑鱼。width height width 2海龟。width 2 height 2石斑鱼。width 3 height 3海豚。width 4 height 4鲸鱼。其余情况不应出现但可忽略。步骤5\texttt{5}5. 输出统计结果。算法时间复杂度O(L×C)O(L \times C)O(L×C)空间O(L×C)O(L \times C)O(L×C)。代码实现// Shark// UVa ID: 830// Verdict: Accepted// Submission Date: 2018-03-14// UVa Run Time: 0.000s//// 版权所有C2018邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;chargrid[70][70];intL,C;intleftC,rightC,topL,bottomL,area;intoffset[4][2]{{1,0},{-1,0},{0,1},{0,-1}};voidfloodFill(inti,intj,charoldChar,charnewChar){if(grid[i][j]oldChar){area;grid[i][j]newChar;leftCmin(leftC,j),rightCmax(rightC,j),topLmin(topL,i),bottomLmax(bottomL,i);for(intk0;k4;k){intiiioffset[k][0],jjjoffset[k][1];if(ii1iiLjj1jjC)floodFill(ii,jj,oldChar,newChar);}}}intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases;cincases;for(intc1;ccases;c){cinLC;for(inti1;iL;i){for(intj1;jC;j)cingrid[i][j];// 输入末尾可能有多余的空格若不加此语句评测结果为 Wrong Answer。cin.ignore(1024,\n);}intsardines0,mackerels0,salmons0,groupers0,turtles0,dolphines0,whales0,sharks0;for(inti1;iL;i)for(intj1;jC;j)if(grid[i][j]!.){leftCC,rightC1,topLL,bottomL1,area0;floodFill(i,j,grid[i][j],.);intwidthabs(topL-bottomL)1,heightabs(leftC-rightC)1;if(area!width*height)sharks;else{if(widthheight)swap(width,height);if(width1height1){sardines;continue;}if(width1height2){mackerels;continue;}if(width1height2){salmons;continue;}if(widthheightwidth2){turtles;continue;}if(width2height2){groupers;continue;}if(width3height3){dolphines;continue;}if(width4height4){whales;continue;}}}if(c1)cout\n;coutsardines mackerels salmons groupers turtles dolphines whales sharks\n;}return0;}总结本题通过Flood Fill\texttt{Flood Fill}Flood Fill获取每个连通块的边界矩形和面积利用面积与矩形面积的比较区分鲨鱼与其他规则形状再根据矩形尺寸精确分类其他动物。由于动物形状由规则定义分类逻辑清晰。代码中直接将网格字符读入忽略空行适合输入格式。该解法时间复杂度O(L×C)O(L \times C)O(L×C)空间O(L×C)O(L \times C)O(L×C)满足网格最大64×6464 \times 6464×64的限制。注意输出时每个测试用例之间有空行且每行八个数字以空格分隔。