题解 P1454 【圣诞夜的极光】

顾z

2018-09-05 14:57:09

Solution

题目描述-->[p1454 圣诞夜的极光](https://www.luogu.org/problemnew/show/P1454) ## 广告: [安利blog](https://www.luogu.org/blog/RPdreamer/#) **题意概括:** 寻找联通块数量,这里的连通块定义与其他的不同. 这里定义为**曼哈顿距离不超过2的都属于一个联通块**. 什么?不知道曼哈顿距离是啥? 曼哈顿距离简易概括->|x1-x2|+|y1-y2|,两点之间横纵坐标的差的绝对值之和. 详细解释->[曼哈顿距离](https://baike.baidu.com/item/%E6%9B%BC%E5%93%88%E9%A1%BF%E8%B7%9D%E7%A6%BB/743092?fr=aladdin) ## 分析 看到大家都在说12个方向,具体是哪12个方向呢? 假设黄色点为我们当前所在节点.那我们图中标出的红色点,都是满足与黄色点**曼哈顿距离为2**的点. ![](https://cdn.luogu.com.cn/upload/pic/31984.png ) 但这才有8个方向啊! 回望题意,**曼哈顿距离不超过2**的都属于一个联通块 曼哈顿距离不超过2,那我们的图应该是这样的↓. (蓝色点即为与黄色点曼哈顿距离为1的. ![](https://cdn.luogu.com.cn/upload/pic/31985.png ) 所以说,现在12个方向就很明确了! 根据标明的坐标,我们很容易打出12个方向对应的位置变化. 像这样↓ ```cpp const int ax[]={-1,-2,1,2,0,0,0,0,1,1,-1,-1}; const int ay[]={0,0,0,0,1,2,-1,-2,1,-1,1,-1}; //const类型可自动识别数组大小. //不过貌似不加const也可以识别 ``` 然后~~我们~~我又遇到了**难题**, **如何输入?** 字符类型,我们一般选择用 scanf("%c"),getchar(),cin来进行输入. 但是这题,用scanf,会出现蜜汁错误.(用scanf只get到了30pts... 而用getchar则会读取行末换行符,需要加判断. 所以我们直接**选用cin来读入字符**.(感觉cin输入字符还是很少出锅的. 因此,我们搜到一个为'#'的位置,就去标记与它在一个联通块中的位置,则联通块个数++即可. **PS:** or ==> || and==> && ---------------------代码-------------------- ```cpp #include<bits/stdc++.h> #define IL inline #define RI register int IL void in(int &x) { int f=1;x=0;char s=getchar(); while(s>'9' or s<'0'){if(s=='-')f=-1;s=getchar();} while(s>='0' and s<='9'){x=x*10+s-'0';s=getchar();} x*=f; } int n,m,ans; char res[108][108]; const int ax[]={-1,-2,1,2,0,0,0,0,1,1,-1,-1}; const int ay[]={0,0,0,0,1,2,-1,-2,1,-1,1,-1}; bool vis[108][108]; IL void dfs(int x,int y) { if(vis[x][y])return; vis[x][y]=true; for(RI i=0;i<12;i++) { int nx=x+ax[i],ny=y+ay[i]; if(nx<1 or ny<1 or nx>n or ny>m )continue; if(res[nx][ny]=='#'and !vis[nx][ny])dfs(nx,ny); } } int main() { in(n),in(m); for(RI i=1;i<=n;i++) for(RI j=1;j<=m;j++) std::cin>>res[i][j]; for(RI i=1;i<=n;i++) for(RI j=1;j<=m;j++) { if(res[i][j]=='#' and !vis[i][j]) { dfs(i,j); ans++; } } printf("%d",ans); } ```