#2 WA 求调。
查看原帖
#2 WA 求调。
1296826
lcfollower楼主2024/8/23 17:35

rt,咕咕咕。。。

#include <bits/stdc++.h>

#define int long long
#define rint register int

using namespace std;

const int N = 1005;
const int fx[8] = {0 ,-1 ,-1 ,-1 ,0 ,1 ,1 ,1} ,fy[8] = {-1 ,-1 ,0 ,1 ,1 ,1 ,0 ,-1};
int vis[N][N] ,vis1[N][N];
int n ,m ,cnt ,tot ,mp[N][N];

struct node{int x ,y ,high;}a[1000005];

inline bool In_Range(int x ,int y){return x >= 1 && y >= 1 && x <= n && y <= n;}
inline void dfs(int x ,int y){
  vis[x][y] = 1;
  for(rint i = 0 ; i < 8 ;i ++){
  	int ax = fx[i] + x ,ay = fy[i] + y;
  	if(In_Range(ax ,ay) && !vis[ax][ay] && mp[ax][ay] <= mp[x][y] && mp[ax][ay] > 0)
  	  dfs(ax ,ay);
  }
} inline void dfs1(int x ,int y){
  vis1[x][y] = 1;
  for(rint i = 0 ; i < 8 ;i ++){
  	int ax = fx[i] + x ,ay = fy[i] + y;
  	if(In_Range(ax ,ay) && !vis1[ax][ay] && mp[ax][ay] >= mp[x][y] && mp[ax][ay] > 0)
  	  dfs1(ax ,ay);
  }
} signed main(){
  scanf("%lld" ,&n);
  for(rint i = 1;i <= n;i ++)
    for(rint j = 1;j <= n;j ++){
      int x;
      scanf("%lld" ,&x);
      mp[i][j] = x;
      if(x) a[++ tot] = {i ,j ,x};
      if(!x) vis[i][j] = vis1[i][j] = -1;
	}
  sort(a + 1, a + 1 + tot ,[](node &s1 ,node &s2){return s1.high > s2.high;});
  for(rint i = 1 ;i <= tot;i ++)
  	if(!vis[a[i].x][a[i].y]) ++ cnt ,dfs(a[i].x ,a[i].y);
  printf("%lld " ,cnt);
  cnt = 0;
  sort(a + 1 , a + 1 + tot ,[](node &s1 ,node &s2){return s1.high < s2.high;});
  for(rint i = 1 ;i <= tot;i ++){
  	if(!vis1[a[i].x][a[i].y]) ++ cnt ,dfs1(a[i].x ,a[i].y);
  }
  printf("%lld\n" ,cnt);
  exit(0);
} 
2024/8/23 17:35
加载中...