acwing 1106 山峰和山谷

简介: acwing 1106 山峰和山谷

活动 - AcWing

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
 
using namespace std ;
 
const int N = 1010 ;
int d[8][2]= {{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1}} ;
int w[N][N] ;
int n , m ;
int ans , res  ;
int c[2] ;
struct node{
  int x , y ;
  node(int xx ,int yy){
    x = xx , y = yy ;
  } 
};
 
queue<node> q ;
int v[N][N] ;
void bfs(int a, int b){
  q.push(node(a,b)) ;
  v[a][b] = 1 ;
  while(!q.empty()){
    node now = q.front() ;
    q.pop() ;
    int x = now.x , y = now.y ;
    for(int i = 0 ; i < 8; i ++){
      int tx = x + d[i][0] , ty = y + d[i][1] ;
      if(tx<0||tx>=n||ty<0||ty>=n) continue ;
      
      if(w[tx][ty]>w[x][y]){
        c[0] = 1 ;
      }
      if(w[tx][ty]<w[x][y]){
        c[1] = 1 ; 
      }
      if(w[tx][ty] == w[x][y]&&!v[tx][ty]){
        v[tx][ty] = 1 ;
        q.push(node(tx,ty)) ;
      }
      
    }
  }
}
int main(){
  cin >> n  ; 
  for(int i = 0 ; i < n ; i ++){
    for(int j = 0 ; j < n ; j ++){
      cin >> w[i][j] ;
    }
  }
  for(int i = 0 ; i < n ;i ++){
    for(int j = 0 ; j < n; j ++){
      if(!v[i][j]){
        c[0]=0 , c[1] = 0 ;
        bfs(i,j);
        if(!c[0]) ans ++;
        if(!c[1]) res ++ ;
      }
    }
  }
  cout << ans << " " << res << endl  ;
}
目录
相关文章
|
2月前
acwing 1098 城堡
acwing 1098 城堡
13 0
|
2月前
acwing 1113 红与黑
acwing 1113 红与黑
10 0
|
2月前
acwing 275 传纸条 (线性dp)
acwing 275 传纸条 (线性dp)
16 0
|
2月前
|
人工智能
AcWing 274. 移动服务(线性dp)
AcWing 274. 移动服务(线性dp)
15 0
|
2月前
acwing 2060 奶牛选美
acwing 2060 奶牛选美
33 0
AcWing 2060. 奶牛选美(每日一题)
AcWing 2060. 奶牛选美(每日一题)
《蓝桥杯每日一题》递推·AcWing 3777. 砖块
《蓝桥杯每日一题》递推·AcWing 3777. 砖块
80 0
|
机器学习/深度学习 人工智能 移动开发
|
机器学习/深度学习 人工智能 移动开发
|
人工智能 BI