본문 바로가기
백준 알고리즘/구현

경사로 C++

by paysmile 2021. 10. 22.

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

 

14890번: 경사로

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

www.acmicpc.net

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
const int MAX = 102;
int n, l;
int map[MAX][MAX];
int answer = 0;

bool CheckWay(vector<int> v) {
	bool flag = false;
	vector<int> visited(n, -1);

	int index;
	for (int j = 0; j < n - 1; j++) {
		index = j;
		while (index <= n - 2 && v[index] == v[index + 1]) {
			index++;
		}
		if (index >= n - 1) {
			flag = true;
			break;
		}
		if (v[index + 1] - v[index] == 1) {
			int count = 0;
			for (int k = index; k >= 0; k--) {
				if (v[index] == v[k] && visited[k] == -1) {
					count++;
				}
				else break;
			}
			if (count >= l) {
				int tmp_i = index;
				for (int k = l; k > 0; k--) {
					visited[tmp_i] = 1;
					tmp_i--;
				}
				j = index;
				if (index == n - 2) {
					flag = true;
					break;
				}
			}
			else break;
		}
		else if (v[index] - v[index + 1] == 1) {
			int count = 0;
			for (int k = index + 1; k < n; k++) {
				if (v[index + 1] == v[k] && visited[k] == -1) {
					count++;
				}
				else break;
			}
			if (count >= l) {
				int tmp_i = index + 1;
				for (int k = l; k > 0; k--) {
					visited[tmp_i] = 1;
					tmp_i++;
				}
				j = index + l - 1;
				if (j == n - 2) {
					flag = true;
					break;
				}
			}
			else break;
		}
		else break;
	}

	return flag;
}

int main(void) {
	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++) {
		vector<int> v;
		v.resize(n);
		for (int j = 0; j < n; j++) {
			v[j] = map[i][j];
		}
		if (CheckWay(v) == true) {
			answer++;
		}
	}

	for (int j = 0; j < n; j++) {
		vector<int> v;
		v.resize(n);
		for (int i = 0; i < n; i++) {
			v[i] = map[i][j];
		}
		if (CheckWay(v) == true) {
			answer++;
		}
	}

	cout << answer << endl;
}

'백준 알고리즘 > 구현' 카테고리의 다른 글

스타트와 링크 C++  (0) 2021.10.22
스타트와 링크 C++  (0) 2021.10.22
감시 C++  (0) 2021.10.22
톱니바퀴 C++  (0) 2021.10.22
치킨 배달 C++  (0) 2021.10.21