P1867 -- ZGG赏极光
时间限制：1000MS
内存限制：131072KB
Description
张格格和他的妹子们来到了北极圣诞区，已经快到12点了。据说极光表演要开始了。这里的极光不是极地特有的自然极光景象。而是人造极光。
轰隆隆……烟花响起。接下来就是极光表演了。
人造极光其实就是空中的一幅幅n*m的点阵图像。只是因为特别明亮而吸引了很多很多格格的目光，也成为了圣诞夜最美丽的一刻。
然而在每幅n*m的点阵图像中，每一个点只有发光和不发光两种状态。对于所有的发光的点，在空中就形成了美丽的图画。而这个图画是以若干个（s个）图案组成的。对于图案， 是有着严格的定义：对于两个发光的点，如果他们的曼哈顿距离（对于A(x1,y1)和B(x2,y2)，A和B之间的曼哈顿距离为|x1-x2|+|y1-y2|）小于等于2。那么这两个点就属于一个图案……
妹子们一边欣赏着极光，一边数着每一幅极光图像中的图案数。伴着歌声和舞蹈，度过了美丽的圣诞之夜。
Input Format
第一行，两个数n和m。
接下来一共n行，每行m个字符。对于第i行第j个字符，如果其为“-”，那么表示该点不发光，如果其为“#”，那么表示该点发光。不可能出现其他的字符。
Output Format
第一行，一个数s。表示图案数。
Sample Input
19 48 ------------------------------------------------ ---####-----#-----#----------------------####--- --######----#-----#---------------------######-- -########--#-#---#-#####--#-##-##---#--########- -###--###--#-#---#-#----#-##-##--#--#--###--###- -###--###--#--#-#--######-#--#---#-#---###--###- -########--#--#-#--#------#--#----##---########- --######---#---#---######-#--#-----#----######-- ---####----------------------------#-----####--- ----------------------------------#------------- ------------------------------------------------ ---###--#--------#------#----------------------- --#---#-#---------------#----------------------- -#------#-##--#-##--##-###-#-##-###--###-#--##-- -#------##--#-##-#-#----#--##--#---##---##-#---- -#------#---#-#--#--#---#--#---#---##----#--#--- --#---#-#---#-#--#---#--#--#---#---##---##---#-- ---###--#---#-#--#-##---#--#---#---#-###-#-##--- ------------------------------------------------
Sample Output
4
Hint
1<=n,m<=100
【题解】QAQ加了优化都没有人家不加优化的快，练练搜索基本功：特殊连通块
1 #include<bits/stdc++.h> 2 using namespace std; 3 char a[101][101]; 4 char B[1<<15],*S=B,*T=B; 5 int dx[]={0,0,0,0,1,2,-1,-2,-1,1,-1,1}; 6 int dy[]={-1,-2,1,2,0,0,0,0,-1,1,1,-1}; 7 int n,m,cnt; 8 char getchar2() { 9 return S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++; 10 } 11 int read() { 12 int x=0,f=1; 13 char ch=getchar2(); 14 while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar2();} 15 while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar2();} 16 return x*f; 17 } 18 void filled(int x,int y) { 19 a[x][y]='-'; 20 int xx,yy; 21 for (int i=0;i<=11;++i) { 22 xx=x+dx[i],yy=y+dy[i]; 23 if (a[xx][yy]=='#'&&xx>=1&&yy>=1&&xx<=n&&yy<=m) filled(xx,yy); 24 } 25 } 26 int main() { 27 n=read();m=read(); 28 for (int i=1;i<=n;++i) { 29 for (int j=1;j<=m;++j) a[i][j]=getchar2(); 30 getchar2(); 31 } 32 for (int i=1;i<=n;++i) printf("%s",a[i]); 33 for (int i=1;i<=n;++i) 34 for (int j=1;j<=m;++j) 35 if (a[i][j]=='#') { 36 cnt++; 37 filled(i,j); 38 } 39 printf("%d\n",cnt); 40 return 0; 41 }
