Notice
Recent Posts
Recent Comments
Link
«   2024/05   »
일 월 화 수 목 금 토
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
Tags
more
Archives
Today
Total
관리 메뉴

찌로그

[BOJ] 백준 14890번 경사로 2020_05_22 C++ 본문

Coding

[BOJ] 백준 14890번 경사로 2020_05_22 C++

찌드 2020. 5. 22. 17:07

https://www.acmicpc.net/problem/14890

 

14890번: 경사로

첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.

www.acmicpc.net

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <bits/stdc++.h>
 
using namespace std;
int maps[100][100];
bool lad1[100][100]; // horizontal
bool lad2[100][100]; // vertical
int n, l, answer=0;
 
int verify(int a, int b, string s){
    if(s.length() == 4){// down incline && hor
        int lim = b+l-1;
        if(lim >=n) return -1;
        int pivot = maps[a][b];
        bool flag =false;
        for(int i=b+1; i<b+l; i++){
            if(pivot != maps[a][i]) return -1;
        }
        for(int i=b; i<b+l; i++){
            if(lad1[a][i] == 1) return -1;
            lad1[a][i] = 1; // visited
        }
        return b+l-1;
    }
    else if(s.length() == 2){ // up incline && hor
        int lim = b-l;
        if(lim <0) return -1;
        int pivot = maps[a][b-1];
        bool flag = false;
        for(int i=b-2; i>=b-l; i--){
            if(pivot != maps[a][i]) return -1;
        }
        for(int i=b-1; i>=b-l; i--){
            if(lad1[a][i] == 1) return -1;
            lad1[a][i] =1;
        }
        return b;
    }
}
int verify2(int a, int b, string s){
    //cout << a <<endl;
    if(s.length() == 4){// down incline && ver
        int lim = a+l-1;
        if(lim >=n) return -1;
        int pivot = maps[a][b];
        bool flag =false;
        for(int i=a+1; i<a+l; i++){
            if(pivot != maps[i][b]) return -1;
        }
        for(int i=a; i<a+l; i++){
            if(lad2[i][b] == 1) return -1;
            lad2[i][b] = 1; // visited
        }
 
        return a+l-1;
    }
    else if(s.length() == 2){ // up incline && ver
        int lim = a-l;
        if(lim <0) return -1;
        int pivot = maps[a-1][b];
        bool flag = false;
        for(int i=a-2; i>=a-l; i--){
            if(pivot != maps[i][b]) return -1;
        }
        for(int i=a-1; i>=a-l; i--){
            if(lad2[i][b] == 1) return -1;
            lad2[i][b] =1;
        }
        return a;
    }
 
 
}
void sear(){
    for(int i=0; i<n; i++){
        int x = maps[i][0];
        bool flag = true;
        int j=1;
 
        while(j < n){// for(int j=1; j<n; j++){
            if(abs(maps[i][j] - maps[i][j-1])> 1){
                flag = false;
                break;
            }
            else if(x > maps[i][j]){ // down incline
                int ret = verify(i,j, "down");
                if(ret <0) {flag = false; break;}
                else{
                    j = ret;
                    x = maps[i][j];
                    continue;
                }
            }else if(x < maps[i][j] ){ // up incline
                int ret = verify(i,j, "up");
                if(ret <0) {flag = false; break;}
                else{
                    j = ret;
                    x = maps[i][j];
                    continue;
                }
            }
            j++;
        }
        if(flag)    answer++;
    }
 
    for(int j=0; j<n; j++){
        int x = maps[0][j];
        bool flag = true;
        int i=1;
 
        while(i < n){// for(int j=1; j<n; j++){
            if(abs(maps[i-1][j] - maps[i][j])> 1){
                flag = false;
                break;
            }
            else if(x > maps[i][j]){ // down incline
                int ret = verify2(i,j, "down");
                if(ret <0) {flag = false; break;}
                else{
                    i = ret;
                    x = maps[i][j];
                    continue;
                }
            }else if(x < maps[i][j] ){ // up incline
                int ret = verify2(i,j, "up");
                if(ret <0) {flag = false; break;}
                else{
                    i = ret;
                    x = maps[i][j];
                    continue;
                }
            }
            i++;
        }
        if(flag)    answer++;
    }
    cout << answer <<endl;
}
void input(){
    cin >> n >> l;
    for(int i=0; i<n; i++) for(int j=0; j<n; j++) cin >>  maps[i][j];
}
int main(){
    input();
    sear();
    return 0;
}
 
cs

'Coding' 카테고리의 다른 글

[BOJ] 백준 15683번 감시 2020_05_26 C++  (0) 2020.05.26
[BOJ] 백준 14891번 톱니바퀴 2020_05_22 C++  (0) 2020.05.22
[BOJ] 백준 17825번 주사위 윷놀이 2020_05_21 C++  (0) 2020.05.21
[BOJ] 백준 17822번 문제 원판 돌리기 2020_05_19 C++  (0) 2020.05.19
[BOJ] 백준 15684번 문제 사다리 조작 2020_05_19 C++  (0) 2020.05.19
'Coding' Related Articles more
Comments