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

作者注

图片来自

http://www.cnblogs.com/wangck/p/4294282.html

题目大意

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

问有多少个太阳，并统计每个太阳周围的光线数量，排序后输出。

图的规模是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

作者注

题目大意

题解

代码

发表回复 取消回复

发表回复取消回复