#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#define ll long long
#define ull unsigned long long
using namespace std;
int N, L, ans;
int board[101][101];
bool horizon(int i){
int prev = board[i][0];
bool flag = true;
int preCnt = 1;
bool check[N];
fill(check, check+N, false);
for(int a=1;a<N;a++)
{
if(abs(prev - board[i][a]) > 1){
flag = false;
break;
}
if(board[i][a] > prev){
if(preCnt >= L){
preCnt = 1;
}
else{
flag = false;
break;
}
}else if(board[i][a] < prev){
int cnt=0;
for(int q=a;q<N;q++)
{
if(cnt >= L) break;
if(board[i][q] != board[i][a]) break;
else cnt++;
}
if(cnt < L){
flag = false;
break;
}
preCnt = -L+1;
}else{
preCnt++;
}
prev = board[i][a];
}
if(flag == true) return true;
else return false;
}
bool vertical(int i){
int prev = board[0][i];
bool flag = true;
int preCnt = 1;
bool check[N];
fill(check, check+N, false);
for(int a=1;a<N;a++)
{
if(abs(prev - board[a][i]) > 1){
flag = false;
break;
}
if(board[a][i] > prev){
if(preCnt >= L){
preCnt = 1;
}
else{
flag = false;
break;
}
}else if(board[a][i] < prev){
int cnt=0;
for(int q=a;q<N;q++)
{
if(cnt >= L) break;
if(board[q][i] != board[a][i]) break;
else {
check[q] = true;
cnt++;
}
}
if(cnt < L){
flag = false;
break;
}
preCnt = -L+1;
}else{
preCnt++;
}
prev = board[a][i];
}
if(flag == true) return true;
else return false;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.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++)
{
bool flagH = horizon(i);
if(flagH) ans++;
bool flagV = vertical(i);
if(flagV) ans++;
}
cout << ans;
return 0;
}
- 핵심 로직
이전 블록의 값인 prev
와 다음 블록의 값
을 비교
해서 큰 경우
와 작은 경우
로 나누어서 처리
(값의 차
가 1 이상
이면 경사로를 놓을 수 없으니
바로 종료
)
작은 경우
작은쪽
에 경사로
를 놓아야 하기 때문에 다음 블록을 포함
해 앞으로 최소 L개의 같은 값
이 있어야 함
(반복문
을 통해서 앞으로 L-1개
가 다음 블록의 값
과 일치하는지 검사
)
현재
까지 연속된 같은 블록
을 세는 preCnt 개수
를 (-L+1)개
로 설정해줘야 한다
--> 다음 블록 포함 L개
는 경사로를 만들기 위해 사용
되기 때문에 카운트하면 안됨
! (핵심!!)
큰 경우
같은 값을 가리키는 preCnt
가 L보다 크거나 같으면
경사로를 놓을 수 있음!
- 정리
prev
가 다음 블록
보다 작은 경우
preCnt = -L+1
로 해주는 것이 핵심
--> 다음 블록 포함 L개
는 경사로를 만들기 위해 사용
됨을 표기
해야 하기 때문
vertical
과 horizon
은 기능은 같고 검사
하는 위치만 다름