[구현 알고리즘] 경사로 / G3

특별할 게 없는 구현 문제다

 

각 줄에 대한 알고리즘은 다음과 같다

 

1. 이전 값보다 큰 값이 나오면 이전 L칸이 한칸 작은 칸인지 확인 후 check배열에 체크

2. 이전 값보다 작은 값이 나오면 다음 L칸이 한칸 작은 칸인지 확인 후 check 배열에 체크

 

#include<bits/stdc++.h>
using namespace std;
int n, l;
int cnt;
int board[101][101];

bool checkRow(int row){
    bool check[101] = {false, };
    int ex = board[row][0];
    //cout <<board[row][0]<<"\n";
    for (int i = 1;i < n;i++) {
        //cout << board[row][i] << "\n";
        if (ex < board[row][i]) {
            //cout << "mountain!\n";
            if (i - l < 0) return false;
            else {
                int gap = abs(ex - board[row][i]);
                if (gap != 1) return false;
                bool possible = true;
                for (int j = i - l;j < i;j++) {
                    if (board[row][j] != ex || check[j]) {
                        possible = false;
                        break;
                    }
                }
                if (possible) {
                    for (int j = i - l;j < i;j++) {
                        //cout << "buliding bridge at " << row << ", " << j << "\n";
                        check[j] = true;
                    }
                }
                else return false;
            }
            ex = board[row][i];
        }
        else if (ex > board[row][i]) {
            //cout << "slope!\n";
            if (i + l-1 >=n) return false;
            else {
                int gap = abs(ex - board[row][i]);
                if (gap != 1) return false;
                bool possible = true;
                for (int j = i;j < i+l;j++) {
                    if (board[row][j] != board[row][i] || check[j]) {
                        possible = false;
                        break;
                    }
                }
                if (possible) {
                    for (int j = i;j < i+l;j++) {
                        //cout << "buliding bridge at " << row << ", " << j << "\n";
                        check[j] = true;
                    }
                }
                else return false;
            }
            ex = board[row][i];
            i += (l - 1);
        }
    }
    //cout << "Row "<<row<<" OK!\n";
    return true;
}   
bool checkCol(int col) {
    bool check[101] = { false, };
    int ex = board[0][col];
    //cout << board[0][col] << "\n";
    for (int i = 1;i < n;i++) {
        //cout << board[i][col] << "\n";
        if (ex < board[i][col]) {
            //cout << "mountain!\n";
            if (i - l < 0) return false;
            else {
                int gap = abs(ex - board[i][col]);
                if (gap != 1) return false;
                bool possible = true;
                for (int j = i - l;j < i;j++) {
                    if (board[j][col] != ex || check[j]) {
                        possible = false;
                        break;
                    }
                }
                if (possible) {
                    for (int j = i - l;j < i;j++) {
                        //cout << "buliding bridge at " << col << ", " << j << "\n";
                        check[j] = true;
                    }
                }
                else return false;
            }
            ex = board[i][col];
        }
        else if (ex > board[i][col]) {
            //cout << "slope!\n";
            if (i + l - 1 >= n) return false;
            else {
                int gap = abs(ex - board[i][col]);
                if (gap != 1) return false;
                bool possible = true;
                for (int j = i;j < i + l;j++) {
                    if (board[j][col] != board[i][col] || check[j]) {
                        possible = false;
                        break;
                    }
                }
                if (possible) {
                    for (int j = i;j < i + l;j++) {
                        //cout << "buliding bridge at " << col << ", " << j << "\n";
                        check[j] = true;
                    }
                }
                else return false;
            }
            ex = board[i][col];
            i += (l-1);
        }
    }
    //cout << "Col "<<col<<" OK!\n\n";
    return true;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> l;
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < n;j++) {
            cin >> board[i][j];
        }
    }
    for (int i = 0;i < n;i++) {
        if (checkRow(i)) cnt++;
        if (checkCol(i)) cnt++;
    }
    cout << cnt;
    return 0;
}
/*
    
    각 줄에 대해 
        이전과 다른 원소가 들어오면 
            1. -L만큼 동일한 원소이고, 1만큼 작은 원소인지
                맞다면 경사로 설치 : bool check[][]를 통해
        이전보다 큰 원소가 들어오면
            이전에 설치

            이전보다 작은 원소가 들어오면
                다음에 설치

    
    
*/