[CF 316F3]Suns and Rays解题报告

作者注

图片来自


题目大意

给出一张位图,是太阳和周围的光芒,像这样:

问有多少个太阳,并统计每个太阳周围的光线数量,排序后输出。
图的规模是1600*1600,光线的宽度<=3.保证太阳不会太小,光线也不会太短。

题解

这题挺有意思。
首先将白色“收缩”:如果一个点的周围有黑色,就将它变成黑的。重复若干次。


就变成了这样。

然后“扩张”,即逆操作:若周围有白的就把它变成白的。


(注意每个白色区域都变大了)

我们可以在这张图中找出所有太阳的“核心部分”,并给它们标号。

用原图减掉这张图,得到:



这样就把所有的光线独立了出来。对它们进行floodfill即可。

注意,最后可能有一些小块,判断一下,如果规模太小就不认为是光线即可。

代码


#include
#include
#include
#include
#include
using namespace std;
const int DIR_NUM=4;
const int SIZEH=1610,SIZEC=100010;
int H,W;
int C;//核心数量
int board[SIZEH][SIZEH];
int core[SIZEH][SIZEH];
int sun[SIZEH][SIZEH];
int raynum[SIZEC]={0};
int dx[]={0,0,1,-1,1,1,-1,-1},dy[]={1,-1,0,0,1,-1,1,-1};
void print(int s[SIZEH][SIZEH]){
	for(int i=0;i0) ans=sun[x1][y1];
			else if(sun[x1][y1]==0){
				int tp=DFS_ray(x1,y1);
				if(tp) ans=tp;
			}
		}
	}
	return ans;
}
void Find_Ray(void){
	for(int i=0;i=5) raynum[t]++;
			}
		}
	}
}
void DFS_core(int x,int y,int col){
	core[x][y]=col;
	for(int d=0;d=0&&f[i1][j1]>0) g[i][j]=f[i1][j1];
				}
			}
		}
	}
}
void Multiple_Sun_Recover(int f[SIZEH][SIZEH],int tim){
	static int g[SIZEH][SIZEH];
	for(int i=1;i<=tim;i++){
		Sun_Recover(f,g);
		memcpy(f,g,sizeof(g));
	}
}
void Work(void){
	int width=3;//三次就能消去所有光束
	memcpy(core,board,sizeof(core));
	Multiple_Background_Spread(core,width);
	Find_Core();
	memcpy(sun,core,sizeof(sun));
	Multiple_Sun_Recover(sun,width);
	Find_Ray();
	sort(raynum+1,raynum+1+C);
	printf("%d\n",C);
	for(int i=1;i<=C;i++) printf("%d ",raynum[i]);
	printf("\n");
}
void Read(void){
	scanf("%d%d",&H,&W);
	for(int i=0;i

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注