[SW Expert Academy] - 활주로 건설

#include<iostream>
#include<cstring>
using namespace std;

int n,k;
int map[20][20];
int chk[20][20];

// 가로방향
bool dfs(int x, int y){
    if( y == n-1 )
        return true;
    if( map[x][y] == map[x][y+1] )
        return dfs(x,y+1);
    // 내리막
    else if( map[x][y] == map[x][y+1] + 1 ){
        if( y + k >= n) // 범위 초과
            return false;
        for(int i=1; i<=k; i++){
            chk[x][y+i] = 1;
            if(map[x][y] != map[x][y+i] + 1)
                return false;
        }
        return dfs(x,y+k);
    }
    // 오르막
    else if( map[x][y] == map[x][y+1] - 1 ){
        if( y-k+1 < 0) // 범위 초과
            return false;
        for(int i=0; i<k; i++){
            if(chk[x][y-i]) // 이미 설치됨
                return false;
            chk[x][y-i] = 1;
            if(map[x][y] != map[x][y-i]){
                return false;
            }
        }
        return dfs(x,y+1);
    }
    return false;
}

// 세로방향
bool dfs2(int x, int y){
    if( x == n-1 )
        return true;
    
    if( map[x][y] == map[x+1][y] )
        return dfs2(x+1,y);
    
    // 내리막
    else if( map[x][y] == map[x+1][y] + 1 ){
        if( x + k >= n) // 범위 초과
            return false;
        for(int i=1; i<=k; i++){
            chk[x+i][y] = 1;
            if(map[x][y] != map[x+i][y] + 1)
                return false;
        }
        return dfs2(x+k,y);
    }
    // 오르막
    else if( map[x][y] == map[x+1][y] - 1 ){
        if( x-k+1 < 0) // 범위 초과
            return false;
        for(int i=0; i<k; i++){
            if(chk[x-i][y]) // 이미 설치됨
                return false;
            chk[x-i][y] = 1;
            if(map[x][y] != map[x-i][y]){
                return false;
            }
        }
        return dfs2(x+1,y);
    }
    return false;
}

int main(){
    int TC;
    cin >> TC;
    
    for(int tc=1; tc<=TC; tc++){
        cin >> n >> k;
        memset(map, 0, sizeof(map));
        for(int i=0; i<n; i++) for(int j=0; j<n; j++) scanf("%d",&map[i][j]);
        
        int ans = 0;
        // 가로
        memset(chk, 0, sizeof(chk));
        for(int i=0; i<n; i++){
            if( dfs(i,0) )
                ans++;
        }
        
        // 세로
        memset(chk, 0, sizeof(chk));
        for(int i=0; i<n; i++){
            if( dfs2(0,i))
                ans ++;
        }
        printf("#%d %d\n",tc,ans);
    }
    return 0;
}