[14890] 경사로

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

지도가 주어졌을 때

행이나 열로 이루어진 길 중 지나갈 수 있는 길은 모두 몇 개인지 묻는 문제이다.

우리는 경사진 곳에 길이가 L인 경사로를 설치해 길을 지나갈 수 있도록 만들 수 있다.

경사로 설치에는 조건이 필요하다.

1. 경사로는 높이가 1 이기 때문에 높이가 2 이상인 곳은 경사로를 설치할 수 없다.

2. 길이가 L인 평평한 땅이 필요하다.

3. 경사로를 겹쳐서 설치할 수 없다.

이 조건들만 조심해서 코드를 작성하면 된다.

먼저 첫 번째 조건은 간단하다.

경사로가 차이가 났을 때 둘의 차이가 2 이상 나는지 확인해주면 된다.

두 번째 조건은 생각보다 복잡하다.

먼저 경사로를 설치할 땅이 남아있는지 확인한다. 

오르막 경사와 내리막 경사에 따라 경사로를 설치 했을 때 

길이 끝나는 지점인지 아닌지 확인 하면 된다.

설치할 땅이 남아있으면 그 곳까지의 경사 값이 모두 같은지 확인한다.

세 번째 조건은 위의 두번 째 조건 중에 땅을 확인하면서 이미 경사로가 설치되어 있는

땅인지 아닌지를 확인해주면 된다.

많이 어려운 문제는 아니지만

시뮬레이션 문제 답게 범위 조절이 어려울 수 있다.

이런 문제는 직접 손으로 해보는 것이 더 빠르다.

끝.

#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int n, l;
int arr[110][110], visit[110][110];
int row(int pos) {
    memset(visit, 0, sizeof(visit));
    for (int i = 1; i<n; i++) {
        if (abs(arr[pos][i] - arr[pos][i-1]) >= 2) return false;
        if ((arr[pos][i] - arr[pos][i-1]) == 1) { //오르막 경사
            if (i - l < 0) return false; //길이 남아있는지 확인
            int cur = arr[pos][i - 1];
            for (int k = i - 1; k >= i - l; k--) { //경사로 설치
                if (visit[pos][k]) return false; //이미 설치되어 있는지 확인
                visit[pos][k] = 1;
                if (cur == arr[pos][k]) continue;
                else false;
            }
        }
        else if ((arr[pos][i-1] - arr[pos][i]) == 1) { //내리막 경사
            if (i + l > n) return false;
            int cur = arr[pos][i];
            for (int k = i; k < i + l; k++) {
                if (visit[pos][k]) return false;
                visit[pos][k] = 1;
                if (cur == arr[pos][k]) continue;
                else false;
            }
        }
    }
    return true;
}
 
int col(int pos) {
    memset(visit, 0, sizeof(visit));
    for (int i = 1; i<n; i++) {
        if (abs(arr[i-1][pos] - arr[i][pos]) >= 2) return false;
        if ((arr[i][pos] - arr[i-1][pos]) == 1) { //오르막 경사
            if (i - l < 0) return false;
            int cur = arr[i - 1][pos];
            for (int k = i - 1; k >= i - l; k--) {
                if (visit[k][pos]) return false;
                visit[k][pos] = 1;
                if (cur == arr[k][pos]) continue;
                else false;
            }
        }
        else if ((arr[i-1][pos] - arr[i][pos]) == 1) { //내리막 경사
            if (i + l > n) return false;
            int cur = arr[i][pos];
            for (int k = i; k < i + l; k++) {
                if (visit[k][pos]) return false;
                visit[k][pos] = 1;
                if (cur == arr[k][pos]) continue;
                else false;
            }
        }
    }
    return true;
}
 
int main() {
    scanf("%d %d", &n, &l);
    for (int i = 0; i<n; i++) {
        for (int j = 0; j<n; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
    int ans = 0;
    for (int i = 0; i<n; i++) {
        if (row(i)) {
            ans++;
        }
        if (col(i)) {
            ans++;
        }
    }
    printf("%d\n", ans);
 
    return 0;
}