백준 14890번 경사로 C++

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

 

건물의 높이와 경사로를 설치했는지 여부를 저장하는 2차원 배열을 만들었다.

그리고 모든 경사로를 같이 설치하는게 아니라 지나갈 수 있는 길의 개수를 구하는 것이기 때문에 한 행이나 열을 구한 뒤 설치한 경사로를 다시 초기화 해주면서 문제를 해결하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

int n, l;

enum class Dir {
	Right,
	Down
};

void RefreshBoard(vector<vector<pair<int, bool>>>& board, int load, Dir dir) {
	if (dir == Dir::Right) {
		for (int i = 0; i < n; i++) {
			board[load][i].second = false;
		}
	}
	else if (dir == Dir::Down) {
		for (int i = 0; i < n; i++) {
			board[i][load].second = false;
		}
	}
}

void Install(vector<vector<pair<int, bool>>>& board, int load, int start, int end, Dir dir) {
	if (dir == Dir::Right) {
		for (int i = start; i < end; i++) {
			board[load][i].second = true;
		}
	}
	else if (dir == Dir::Down) {
		for (int i = start; i < end; i++) {
			board[i][load].second = true;
		}
	}
}

bool PossibleToInstall(vector<vector<pair<int, bool>>> &board, int load, 
						int start, int end, int height, Dir dir) {
	if (dir == Dir::Right) {
		for (int i = start; i < end; i++) {
			if (i >= n || i < 0) return false;
			if (board[load][i].first != height) return false;
			if (board[load][i].second) return false;
		}
	}
	else if (dir == Dir::Down) {
		for (int i = start; i < end; i++) {
			if (i >= n || i < 0) return false;
			if (board[i][load].first != height) return false;
			if (board[i][load].second) return false;
		}
	}
	Install(board, load, start, end, dir);
	return true;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int cnt = 0;
	cin >> n >> l;
	vector<vector<pair<int, bool>>> board(n, vector<pair<int, bool>>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int height;
			cin >> height;
			board[i][j] = { height,false };
		}
	}
	for (int i = 0; i < n; i++) {
		int lastRightHeight = board[i][0].first;
		int lastDownHeight = board[0][i].first;
		bool right = true;
		bool down = true;
		for (int j = 0; j < n; j++) {
			int currHeight = board[i][j].first;
			if (board[i][j].second) {
				lastRightHeight = currHeight;
				continue;
			}
			if (lastRightHeight != currHeight) {
				bool isPossible;
				if (lastRightHeight - currHeight == 1) {
					isPossible = PossibleToInstall(board, i, j, j + l, currHeight, Dir::Right);
				}
				else if (currHeight - lastRightHeight == 1) {
					isPossible = PossibleToInstall(board, i, j - l, j, lastRightHeight, Dir::Right);
				}
				else isPossible = false;

				if (isPossible == false) right = false;
			}
			if (right == false) break;
			lastRightHeight = currHeight;
		}
		RefreshBoard(board, i, Dir::Right);
		for (int j = 0; j < n; j++) {
			int currHeight = board[j][i].first;
			if (board[j][i].second) {
				lastDownHeight = currHeight;
				continue;
			}
			if (lastDownHeight != currHeight) {
				bool isPossible;
				if (lastDownHeight - currHeight == 1) {
					isPossible = PossibleToInstall(board, i, j, j + l, currHeight, Dir::Down);
				}
				else if (currHeight - lastDownHeight == 1) {
					isPossible = PossibleToInstall(board, i, j - l, j, lastDownHeight, Dir::Down);
				}
				else isPossible = false;

				if (isPossible == false) down = false;
			}
			if (down == false) break;
			lastDownHeight = currHeight;
		}
		RefreshBoard(board, i, Dir::Down);
		if (right) cnt++;
		if (down) cnt++;
	}
	cout << cnt;
};