백준 문제 14890번 경사로 문제풀이 c++
https://www.acmicpc.net/problem/14890
14890번: 경사로
첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.
www.acmicpc.net
문제해석
경사로를 놓고 지나갈 수 있는 길이 몇개인지 찾는 그냥 구현문제이다.
그런데 어떻게 할지 몰라서 생각나는대로 그냥 막 구현했다..
아이디어는 이렇다.
각 행마다
1.왼쪽에서 오른쪽
2.오른쪽에서 왼쪽
각열마다
3.위쪽에서 아래쪽
4.아래쪽에서 위
길을 갈 수있는 경우가 이렇게 있는데
a.1 1이 가능하면 그 행은 갈 수있는 길이므로 ans값을 1증가
a.2 1이 불가능하면 2를 확인한다.
a.2.1 2가 가능하면 갈 수있는 길이므로 ans값을 1증가
a.2.2 2도 불가능하면 그 행은 왼쪽에서 오른쪽이든 오른쪽에서 왼쪽이든 갈 수 없는 길이다.
b.1 3이 가능하면 그 열은 갈 수있는 길이므로 ans값을 1증가
b.2 3이 불가능하면 4를 확인한다.
b.2.1 4가 가능하면 갈 수있는 길이므로 ans값을 1증가
b.2.2 4도 불가능하면 그 열은 위쪽에서 아래쪽이든 아래쪽에서 위쪽이든 갈 수 없는 길이다.
높이 차이가 나면 경사로를 놓아야하는데 놓을 수 있는가 없는가를 판단하는 check 함수를 만들어 판단하였다.
놓을 수 있으면 경사로를 이미 놓았다고 b배열에 저장하였다 왜냐면 경사를 겹쳐서 놓을 수는 없다고 문제에서 제시 했기 때문이다.
이걸 그냥 코드로 무식하게 구현하였는데 코드가 너무 길어져서 뭔가 망한 삘이 났는데 다행히 한번에 맞춰서 다행이였다.
코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
bool inside(int ny,int nx);
bool check(int row,int col,int flag);
int a[100][100];
bool b[100];
int n,l;
int main(){
cout.tie(NULL);
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin>>n>>l;
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
cin>>a[i][j];
}
}
int ans=0;
for(int i=0; i<n; i++)
{
memset(b,0,sizeof(b));
for(int j=1; j<n; )
{
if(a[i][j]==a[i][j-1])
{
j++;
}
else
{
if(a[i][j]-a[i][j-1]==1)
{
if(check(i,j,0)==true)
{
j++;
}
else
{
goto Label1;
}
}
else if(a[i][j]-a[i][j-1]==-1)
{
if(check(i,j-1,1)==true)
{
j++;
}
else
{
goto Label1;
}
}
else
{
goto Label1;
}
}
}
ans++;
continue;
Label1:
memset(b,0,sizeof(b));
for(int j=n-2; j>=0; )
{
if(a[i][j]==a[i][j+1])
{
j--;
}
else
{
if(a[i][j]-a[i][j+1]==1)
{
if(check(i,j,1)==true)
{
j--;
}
else
{
goto Label2;
}
}
else if(a[i][j]-a[i][j+1]==-1)
{
if(check(i,j+1,0)==true)
{
j--;
}
else
{
goto Label2;
}
}
else
{
goto Label2;
}
}
}
ans++;
Label2:
continue;
}
////
for(int i=0; i<n; i++)
{
memset(b,0,sizeof(b));
for(int j=1; j<n;)
{
if(a[j][i]==a[j-1][i])
{
j++;
}
else
{
if(a[j][i]-a[j-1][i]==1)
{
if(check(j,i,2)==true)
{
j++;
}
else
{
goto Label3;
}
}
else if(a[j][i]-a[j-1][i]==-1)
{
if(check(j-1,i,3)==true)
{
j++;
}
else
{
goto Label3;
}
}
else
{
goto Label3;
}
}
}
ans++;
continue;
Label3:
memset(b,0,sizeof(b));
for(int j=n-2; j>=0; )
{
if(a[j][i]==a[j+1][i])
{
j--;
}
else
{
if(a[j][i]-a[j+1][i]==1)
{
if(check(j,i,3)==true)
{
j--;
}
else
{
goto Label4;
}
}
else if(a[j][i]-a[j+1][i]==-1)
{
if(check(j+1,i,2)==true)
{
j--;
}
else
{
goto Label4;
}
}
else
{
goto Label4;
}
}
}
ans++;
Label4:
continue;
}
cout<<ans;
}
bool inside(int ny,int nx){
if(0<=ny&&ny<n&&0<=nx&&nx<n)
{
return true;
}
else
{
return false;
}
}
bool check(int row,int col,int flag){
int x;
if(flag==0)
{
for(int i=1; i<=l; i++)
{
if(inside(row,col-i))
{
x=a[row][col-1];
if(x!=a[row][col-i])
{
return false;
}
else
{
if(b[col-i]==1)
{
return false;
}
}
}
else
{
return false;
}
}
for(int i=1; i<=l; i++)
{
b[col-i]=1;
}
return true;
}
else if(flag==1)
{
for(int i=1; i<=l; i++)
{
if(inside(row,col+i))
{
x=a[row][col+1];
if(x!=a[row][col+i])
{
return false;
}
else
{
if(b[col+i]==1)
{
return false;
}
}
}
else
{
return false;
}
}
for(int i=1; i<=l; i++)
{
b[col+i]=1;
}
return true;
}
else if(flag==2)
{
for(int i=1; i<=l; i++)
{
if(inside(row-i,col))
{
x=a[row-1][col];
if(x!=a[row-i][col])
{
return false;
}
else
{
if(b[row-i]==1)
{
return false;
}
}
}
else
{
return false;
}
}
for(int i=1; i<=l; i++)
{
b[row-i]=1;
}
return true;
}
else if(flag==3)
{
for(int i=1; i<=l; i++)
{
if(inside(row+i,col))
{
x=a[row+1][col];
if(x!=a[row+i][col])
{
return false;
}
else
{
if(b[row+i]==1)
{
return false;
}
}
}
else
{
return false;
}
}
for(int i=1; i<=l; i++)
{
b[row+i]=1;
}
return true;
}
}