题解 P1454 【圣诞夜的极光】
顾z
2018-09-05 14:57:09
题目描述-->[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);
}
```