삼성 SW 역량테스트 기출 :: 경사로

문제 링크 : https://www.acmicpc.net/problem/14890

난이도 : 하

 

/*
 * 경사로 https://www.acmicpc.net/problem/14890
 *
 * 가로로 건널 수 있는지 확인하는 함수 하나를 만들고
 * 보드를 회전시켜서 세로도 확인
 */

#include <stdio.h>
#include <iostream>
#include <string.h>

#define FOR(i, n) for(int i = 0 ;i  < n ; i ++)
using namespace std;

int n, l;
int board[100][100];
int rotBoard[100][100];
bool occupied[100][100];
void rotate(){
    FOR(i, n){
        FOR(j, n){
            rotBoard[i][j] = board[n-j-1][i];
        }
    }
}
void init(){
    cin >> n >> l;
    FOR(i, n)
        FOR(j, n)
            scanf("%d",&board[i][j]);
    rotate();
}
// board의 line번 째 줄이 가로로 건널 수 있는지 확인
bool horizontal(int line, int board[100][100]){
    int height = board[line][0];
    for(int i = 1; i<n; i++){
        // 높이가 같으면 상관 없음
        if(board[line][i] == height) continue;
        //다음칸이 한 칸 높으면, 오르막길을 설치할 수 있는지 확인(이전의 l칸이 높이가 모두 height인지)
        else if(board[line][i]==height+1){
            for(int j = 1; j<=l; j++){
                if(i-j<0) return false;
                if(board[line][i-j]!=height) return false;
                if(occupied[line][i-j]) return false; // ***********처음에 경사로가 겹치게 되는 경우를 안빼줘서 틀림
                if(j==l){
                    for(int k = 1; k <= l; k++)
                        occupied[line][i-k] = true;
                    height++;
                }
            }
        }
        //다음칸이 한 칸 낮으면, 내리막길을 설치할 수 있는지 확인(이후의 l칸이 높이가 모두 height-1인지)
        else if(board[line][i]==height-1){
            for(int j = 0 ; j < l ; j ++){
                if(i+j>=n) return false;
                if(board[line][i+j] != height-1) return false;
                if(j==l-1){
                    for(int k = 0; k < l; k++)
                        occupied[line][i+k] = true;
                    height--;
                }
            }
        }
        else return false;
    }
    return true;
}
int main(){
    int total = 0;
    init();
    memset(occupied, false, sizeof(occupied));
    FOR(i, n)
        if(horizontal(i, board)){
//            cout << i << endl;
            total++;
        }
    memset(occupied, false, sizeof(occupied));
    FOR(i, n)
        if(horizontal(i, rotBoard)){
//            cout << i << endl;
            total++;
        }
    cout << total << endl;
}