难道随便打个暴力染色不香吗
by Qing_s @ 2020-10-24 18:18:06
~~又臭又长~~
by Gsmdog_H @ 2020-10-24 18:18:34
@[Qing_s](/user/238735) interesting
by Gsmdog_H @ 2020-10-24 18:26:47
@[Gsmdog_H](/user/313616)
~~very interesting~~
by Qing_s @ 2020-10-24 18:27:51
第一，这个题不用开long long的
第二，你的记忆化搜索其实可以优化掉，直接一边bfs一边设置成已经搜索过就好了
开一下：稍微改了一点点
具体的解析，看[这个](https://www.luogu.com.cn/blog/Psycho-520/ti-xie-p3456-post)
（做个小宣传嘿嘿）
```cpp
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define ll long long
using namespace std;
const int dx[8]={-1,1,0,0,-1,1,-1,1};
const int dy[8]={0,0,-1,1,-1,-1,1,1};
int n;
int high[1010][1010];
bool be[1010][1010];
int ans_f,ans_g;
struct node{
int x,y;
}_find;
queue<node> q;
node pu(int _x,int _y){
node a;
a.x=_x;
a.y=_y;
return a;
}
void bfs(int sx,int sy){
bool flf = 1, flg = 1;
while(!q.empty())
q.pop();
int s=0;
q.push(pu(sx,sy));
while(!q.empty())
{
_find=q.front();
q.pop();
for(int i=0;i<8;i++)
{
int nx=_find.x+dx[i];
int ny=_find.y+dy[i];
if(nx<=0||nx>n||ny<=0||ny>n)
continue;
if(high[nx][ny] > high[_find.x][_find.y] )
flf = 0;
if(high[nx][ny] < high[_find.x][_find.y] )
flg = 0;
if((high[nx][ny]==high[_find.x][_find.y])&&!be[nx][ny])
{
be[nx][ny]=true;
q.push(pu(nx,ny));
}
}
}
if(flf)
ans_f++;
if(flg)
ans_g++;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&high[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(!be[i][j])
bfs(i,j);
printf("%d %d",ans_f,ans_g);
return 0;
}
```
by 苏黎世 @ 2020-10-24 18:29:19
@[苏黎世](/user/307483)
写错了：
开一下,其实是看一下
by 苏黎世 @ 2020-10-24 18:30:12
@[苏黎世](/user/307483)
thanks
```
@[苏黎世](/user/307483)
写错了： 开一下,其实是看一下
```
~~我at我自己¿¿¿~~
by LordLaffey @ 2020-10-24 18:33:41
@[Wmlj__ytm](/user/335136)
未定义行为
by 苏黎世 @ 2020-10-24 18:34:36
@[Wmlj__ytm](/user/335136) ~~笑笑已谢~~
by Qing_s @ 2020-10-24 18:34:54
阿巴阿巴
by Jekyll_Y @ 2020-10-24 18:35:10