[SWEA] 4014. 활주로 건설

▶문제설명

[SWEA] 4014. 활주로 건설

https://www.swexpertacademy.com/main/code/problem/problemSubmitHistory.do?contestProbId=AWIeW7FakkUDFAVH

▶Hint

---

땅의 높이들이 주어진다.

땅의 높이 차가 1인 경우에 경사로를 놓아 활주로를 연결할 수 있다. 

경사로의 높이는 항상 1이며, 세로로 세울 수 없다.

단, 경사로의 길이 X가 주어지는데

활주로를 만드는 과정에서

경사로가 길어서 놓을 공간이 부족한 경우,

경사로가 겹쳐지게 놓이는 경우는 허용하지 않는다.

가로, 세로로 완성될 수 있는 활주로 라인의 개수를 구하는 문제다.

내리막길과 오르막길로 나누어서 생각하고

내리막길일때 경사로를 놓는 경우 그 위치를 체크해두고,

오르막길일때 경사로를 놓는 경우 이미 경사로가 놓여져 있지 않은지 확인하는 과정이 필요하다.

경사로는 겹쳐서 놓을 수 없기 때문이다.

▶Solution

---

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>
using namespace std;
 
int N, X, answer;
int map[20][20];
bool check[20][20];
 
void init() {
    scanf("%d %d", &N, &X);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &map[i][j]);
        }
    }
    answer = 0;
}
 
bool isAbleHD(int r, int c) {
    for (int i = 0; i < X; i++)
    {
        if (c + i == N
            || map[r][c] != map[r][c + i])
        {
            return false;
        }
    }
 
    for (int i = 0; i < X; i++)
        check[r][c + i] = true;
 
    return true;
}
 
bool isAbleHA(int r, int c) {
    for (int i = 0; i < X; i++)
    {
        if (-1 == c - i
            || map[r][c] != map[r][c - i]
            || check[r][c - i] == true)
        {
            return false;
        }
    }
 
    return true;
}
 
bool isAbleVD(int r, int c) {
    for (int i = 0; i < X; i++)
    {
        if (r + i == N
            || map[r][c] != map[r + i][c])
        {
            return false;
        }
    }
 
    for (int i = 0; i < X; i++)
        check[r + i][c] = true;
 
    return true;
}
 
bool isAbleVA(int r, int c) {
    for (int i = 0; i < X; i++)
    {
        if (-1 == r-i
            || map[r][c] != map[r - i][c]
            || check[r - i][c] == true)
        {
            return false;
        }
    }
 
    return true;
}
 
bool checkLineH(int r, int c) {
    
    if (c == N - 1) return true;
 
    if (map[r][c] == map[r][c + 1])
    {
        return checkLineH(r, c + 1);
    }
    
    if (map[r][c] == map[r][c + 1] + 1 
        && isAbleHD(r, c + 1))           // 내리막길
    {
        return checkLineH(r,c + X);
    }
 
    if (map[r][c] == map[r][c + 1] - 1
        && isAbleHA(r, c))              // 오르막길
    {
        return checkLineH(r,c + 1);
    }
 
    return false;
}
 
bool checkLineV(int r, int c) {
 
    if (r == N - 1) return true;
 
    if (map[r][c] == map[r + 1][c])
    {
        return checkLineV(r + 1, c);
    }
 
    if (map[r][c] == map[r + 1][c] + 1
        && isAbleVD(r + 1, c))           // 내리막길
    {
        return checkLineV(r + X, c);
    }
 
    if (map[r][c] == map[r + 1][c] - 1
        && isAbleVA(r, c))              // 오르막길
    {
        return checkLineV(r + 1, c);
    }
 
    return false;
}
 
void solve() {
    //가로
    memset(check, 0, sizeof(check));
    for (int r = 0; r < N; r++) {
        if (checkLineH(r,0))
            answer++;
    }
    //세로
    memset(check, 0, sizeof(check));
    for (int c = 0; c < N; c++) {
        if (checkLineV(0, c))
            answer++;
    }
}
 
int main() {
    int T;
    scanf("%d", &T);
    for(int t = 1 ; t<=T ; t++)
    {
        init();
 
        solve();
 
        printf("#%d %d\n", t, answer);
    }
    return 0;
}