1245 농장 관리

https://www.acmicpc.net/problem/1245

1245번: 농장 관리

 

처음 문제를 볼 때는 풀이를 생각하지 못했는데 정해를 보니 대단했다...

주변에 자신보다 높은 칸이 있다면 false로 바꿔서 ans++을 하지 못하게 한다.

그리고 제일 중요한 점은 자기 자신과 크기가 같은 칸만을 탐색한다는 점이다.

처음에 이를 모르고 풀어서 고생했다.

 

#include <bits/stdc++.h>
using namespace std;
int n,m,ans;
int board[103][73];
bool vis[103][73];
int dx[8]={1,1,0,-1,-1,-1,0,1};
int dy[8]={0,1,1,1,0,-1,-1,-1};
bool isPeak=true;

void BFS(int y, int x){
    queue<pair<int,int>> Q;
    Q.push({y,x}); vis[y][x]=true;
    while(!Q.empty()){
        auto cur=Q.front(); Q.pop();
        for(int dir=0;dir<8;dir++){
            int ny=cur.first+dy[dir];
            int nx=cur.second+dx[dir];
            if(ny<0||nx<0||ny>=n||nx>=m) continue;
            if(board[ny][nx]>board[cur.first][cur.second]) isPeak=false;
            if(vis[ny][nx]||board[ny][nx]!=board[cur.first][cur.second]) continue;
            Q.push({ny,nx}); vis[ny][nx]=true;
        }
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>board[i][j];
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(vis[i][j]) continue;
            isPeak=true;
            BFS(i,j);
            if(isPeak) ans++;
        }
    }
    cout<<ans;
    return 0;
}