문제
https://www.acmicpc.net/problem/14890
풀이
너무너무 오래 걸린 문제다. 구현 능력을 보는 문제 같은데 예외처리 해야될 게 너무 많아 힘들었다.
행과 열 각각 재귀함수로 검사하는 함수를 만들었다.
함수에는 이전 칸의 높이와 동일한 칸의 수를 넘겼다.
이전 칸과 현재 간 사이의 관계는 세 가지로 정의할 수 있다.
- 이전 칸보다 현재 칸이 높은 경우
- 이전 칸보다 현재 칸이 낮은 경우
- 이전 칸과 현재 칸의 높이가 같은 경우
이전 칸과 현재 칸의 차를 구해서 관계를 구했으며 차가 2이상인 경우는 길로 만들 수 없기 때문에 바로 함수를 종료시켰다.
현재 칸이 높은 경우고 차가 1인 경우는 경사로를 만들어야 되는데 이 때 현재까지 쌓인 cnt값을 이용해서 이전에 존재하는 동일한 칸 수가 L 이상인 경우만 L개의 경사로를 만들어줬다.
현재 칸이 낮은 경우고 차가 1인 경우는 현재 칸부터 앞에 L개의 칸을 경사로로 만들어주는데 현재 칸의 높이와 다른 칸이 발견되면 경사로를 만들 수 없게 되고 이 경우는 길이 될 수 없는 경우이기 때문에 함수를 종료시켰다.
마지막 칸까지 검사가 끝나면 n개의 경사로 배열에서 만들어진 경사로의 개수를 파악해서 길이 될 수 있는지 없는지 판단했다.
소스코드
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX_SIZE 101
int n, l;
int map[MAX_SIZE][MAX_SIZE];
int runway_row[MAX_SIZE];
int runway_col[MAX_SIZE];
int ans;
void RecurRow(int prev_h, int x, int y, int cnt)
{
if (y == n)
{
bool isway = true;
for (int i = 0; i < n; i++)
{
if (runway_row[i] > 1)
isway = false;
}
if (isway)
ans++;
memset(runway_row, 0, sizeof(runway_row));
return;
}
int abs_sub = abs(map[x][y] - prev_h);
if (abs_sub == 0)
{
RecurRow(map[x][y], x, y + 1, cnt + 1);
}
else if (abs_sub == 1)
{
if (prev_h < map[x][y])
{
if (cnt >= l)
{
for (int i = y - 1, l_cnt = 0; l_cnt < l; i--, l_cnt++)
{
if (i < 0)
{
memset(runway_row, 0, sizeof(runway_row));
return;
}
runway_row[i] += 1;
}
RecurRow(map[x][y], x, y + 1, 1);
}
else
{
memset(runway_row, 0, sizeof(runway_row));
return;
}
}
else
{
for (int i = y, l_cnt = 0; l_cnt < l; i++, l_cnt++)
{
if (i >= n)
{
memset(runway_row, 0, sizeof(runway_row));
return;
}
if (map[x][i] == map[x][y])
runway_row[i] += 1;
else
{
memset(runway_row, 0, sizeof(runway_row));
return;
}
}
RecurRow(map[x][y], x, y + 1, 1);
}
}
else
{
memset(runway_row, 0, sizeof(runway_row));
return;
}
}
void RecurCol(int prev_h, int x, int y, int cnt)
{
if (x == n)
{
bool isway = true;
for (int i = 0; i < n; i++)
{
if (runway_col[i] > 1)
isway = false;
}
if (isway)
ans++;
memset(runway_col, 0, sizeof(runway_col));
return;
}
int abs_sub = abs(map[x][y] - prev_h);
if (abs_sub == 0)
{
RecurCol(map[x][y], x+1, y, cnt + 1);
}
else if (abs_sub == 1)
{
if (prev_h < map[x][y])
{
if (cnt >= l)
{
for (int i = x - 1, l_cnt = 0; l_cnt < l; i--, l_cnt++)
{
if (i < 0)
{
memset(runway_col, 0, sizeof(runway_col));
return;
}
runway_col[i] += 1;
}
RecurCol(map[x][y], x+1, y, 1);
}
else
{
memset(runway_col, 0, sizeof(runway_col));
return;
}
}
else
{
for (int i = x, l_cnt = 0; l_cnt < l; i++, l_cnt++)
{
if (i >= n)
{
memset(runway_col, 0, sizeof(runway_col));
return;
}
if (map[i][y] == map[x][y])
runway_col[i] += 1;
else
{
memset(runway_col, 0, sizeof(runway_col));
return;
}
}
RecurCol(map[x][y], x+1, y, 1);
}
}
else
{
memset(runway_col, 0, sizeof(runway_col));
return;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> l;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> map[i][j];
}
}
for (int i = 0; i < n; i++)
{
RecurRow(map[i][0], i, 0, 0);
RecurCol(map[0][i], 0, i, 0);
}
cout << ans << "\n";
return 0;
}