백준 14890번: 경사로 (C++)

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

각각의 행과 열에대해서 인덱스가 증가하는 방향으로 한 번, 감소하는 방향으로 두 번 탐색을 진행하면서 예외 처리를 해주었다.

같은 높이가 몇개가 연속되는지 찾아서, 입력으로 주어지는 L과 비교하는 것이 관건인데, 1 1 2 2 이런식으로 증가하는 값에 대한 것은 그 개수를 파악하기 쉽지만, 2 2 1 1 이런식의 수열을 왼쪽에서 순서대로 탐색하면, 번거롭기 때문에 그냥 뒤에서부터도 연속되는 개수를 새서 경우를 따졌다.

/*
cnt == n이면 경로 확정
루프시작 인덱스로 다시 돌아오면 가능 확정

차이가 2이상이면 경로 불가능 확정
cnt < len 인데 증가하면 불가능 확정
경사로 설치한 곳에 또 설치하려고 하면 불가능 확정

*/
#include<iostream>
using namespace std;
int n, len, m[102][102], Rchk[102], Cchk[102];
bool vis[102][102];
int main(void) {
    cin >> n >> len;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> m[i][j];
    
    for (int i = 0; i < n; i++) {
        int cnt = 1;
        for (int j = 1; j < n ; j++) { //col 증가
            if (m[i][j] == m[i][j - 1]) cnt++; //cnt == len이면 확정 -> chk = 1로
            else if (m[i][j] - m[i][j - 1] >= 2) {
                Rchk[i] = -1;
                break;
            }
            else if (m[i][j] > m[i][j - 1] && cnt < len) {
                Rchk[i] = -1;
                break;
            }
            else if (m[i][j] - m[i][j - 1] == 1 && cnt >= len) {
                for (int k = j - 1; k >= j - len; k--) {
                    vis[i][k] = true;
                }
                cnt = 1;
            }
            else if (m[i][j] < m[i][j - 1]) cnt = 1;
            
        }
        if (cnt == n) {
            Rchk[i] = 1;
            continue;
        }
        
        //col 감소
        if (Rchk[i] == -1 || Rchk[i] == 1) continue; //이미 위에서 확정 했으면 스킵
        cnt = 1;
        for (int j = n - 2; j >= 0; j--) {
            bool endFlag = false;
            if (m[i][j] == m[i][j + 1]) cnt++;
            else if (m[i][j] - m[i][j + 1] >= 2) {
                Rchk[i] = -1;
                break;
            }
            else if (m[i][j] > m[i][j + 1] && cnt < len) {
                Rchk[i] = -1;
                break;
            }
            else if (m[i][j] - m[i][j + 1] == 1 && cnt >= len) {
                for (int k = j + 1; k <= j + len; k++) {
                    if (vis[i][k]) {//설치한 곳에 또 설치하려고 하는 경우
                        Rchk[i] = -1;
                        endFlag = true;
                        break;
                    }
                    else
                        vis[i][k] = true;
                }
                if (endFlag) break;
                cnt = 1;
            }
            else if (m[i][j] < m[i][j + 1]) cnt = 1;
            if (j == 0) Rchk[i] = 1;
        }
    }
 
    
    //경사로 놨던거 초기화
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            vis[i][j] = false;
    }
 
 
    for (int i = 0; i < n; i++) {
        int cnt = 1;
        for (int j = 1; j < n; j++) { //col 증가
            if (m[j][i] == m[j-1][i]) cnt++; //cnt == len이면 확정 -> chk = 1로
            else if (m[j][i] - m[j-1][i] >= 2) {
                Cchk[i] = -1;
                break;
            }
            else if (m[j][i] > m[j-1][i] && cnt < len) {
                Cchk[i] = -1;
                break;
            }
            else if (m[j][i] - m[j-1][i] == 1 && cnt >= len) {
                for (int k = j - 1; k >= j - len; k--) {
                    vis[k][i] = true;
                }
                cnt = 1;
            }
            else if (m[j][i] < m[j-1][i]) cnt = 1;
 
 
        }
        if (cnt == n) {
            Cchk[i] = 1;
            continue;
        }
 
        //col 감소
        if (Cchk[i] == -1 || Cchk[i] == 1) continue; //이미 위에서 확정 했으면 스킵
        cnt = 1;
        for (int j = n - 2; j >= 0; j--) {
            bool endFlag = false;
            if (m[j][i] == m[j+1][i]) cnt++;
            else if (m[j][i] - m[j+1][i] >= 2) {
                Cchk[i] = -1;
                break;
            }
            else if (m[j][i] > m[j+1][i] && cnt < len) {
                Cchk[i] = -1;
                break;
            }
            else if (m[j][i] - m[j+1][i] == 1 && cnt >= len) {
                for (int k = j + 1; k <= j + len; k++) {
                    if (vis[k][i]) {//설치한 곳에 또 설치하려고 하는 경우
                        Cchk[i] = -1;
                        endFlag = true;
                        break;
                    }
                    else
                        vis[k][i] = true;
                }
                if (endFlag) 
                    break;
                
                cnt = 1;
            }
            else if (m[j][i] < m[j+1][i]) cnt = 1;
            if (j == 0) Cchk[i] = 1;
        }
    }
    
    int res = 0;
    for (int i = 0; i < n; i++) {
        if (Rchk[i] == 1) res++;
        if (Cchk[i] == 1) res++;
    }
    cout << res;
 
    return 0;
}