1122

n * m 크기의 직사각형 모양의 지역이 있다. 이 지역은 크기가 1 * 1인 정사각형 모양의 땅으로 구분되어 있다. 땅에 지어진 건물의 높이가 주어질 때, 인접한 상하좌우 위치의 모든 건물보다 높이가 높은 건물의 개수는 몇 개인지 구하는 프로그램을 작성하시오.
 
참고) 색칠한 건물의 상하좌우 건물은 다음과 같다.

건물	건물 (상)	건물
건물 (좌)	건물	건물 (우)
건물	건물 (하)	건물

첫 줄에 정수 n과 m이 주어진다. n은 행의 개수, m은 열의 개수이다. (1≦n, m≦100)
다음 n개의 줄에는 m개의 정수 a_i가 공백으로 구분되어 입력된다. a_i는 각 땅에 지어진 건물 높이다.
(1≦ a_i ≦10,000, i=1,2,3,...,m)

인접한 상하좌우 위치의 건물보다 높은 건물의 개수를 출력한다.

각 건물의 높이를 2차원 배열에 저장했을 때, 배열 (i, j) 인덱스에 있는 건물과 인접한 건물을 표시하면 다음과 같다.

건물	건물 (i-1, j)	건물
건물 (i, j-1)	건물	건물 (i, j+1)
건물	건물 (i+1, j)	건물

 
상하좌우를 탐색할 때는 다음과 같이 dy, dx 배열을 만들고 반복문으로 돌리면 탐색하고자 하는 위치를 쉽게 구할 수 있다. 다음과 같은 탐색 처리는 잘 알아두는 것이 좋다.

int dy[] = {-1, 0, 1, 0};
int dx[] = {0, -1, 0, 1};
for(int k=0; k<4; k++){ // (i,j)인덱스의 상하좌우 값 구하기
    int y = i+dy[k];
    int x = j+dx[k];
}

k가 0일 때, (i – 1, j)
k가 1일 때, (i, j - 1)
k가 2일 때, (i + 1, j)
k가 3일 때,(i, j + 1)
2차원 배열의 각 요소에 대하여 상하좌우 위치의 요소와 값을 비교한다. 이 때, 배열의 인덱스를 벗어나는지 확인해야 한다.
또한, 상하좌우 위치 한 곳에서라도 현재 건물보다 더 높은 곳이 있다면 break를 걸어 상하좌우 탐색을 종료한다.

for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
        bool flag = true;
        for(int k=0; k<4; k++){ // arr[i][j] 건물의 상하좌우 탐색 시작
            int y = i+dy[k]; // 인접한 행 위치 구하기
            int x = j+dx[k]; // 인접한 열 위치 구하기
            if(y < 0 || y >= n || x < 0 || x >= m) // 인덱스를 벗어나면 continue;
                continue;
            if(arr[i][j] <= arr[y][x]){ // 상하좌우 위치 중 한 곳에서라도 더 크다면 break;
                break;
            flag = false;
        }
    }
    if(flag) // flag가 true면 현재 arr[i][j]의 건물 높이는 상하좌우 모든 건물보다 높다.
    cnt++;
}