c++ 백준_1245_"농장 관리"

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

1245번: 농장 관리

 

조건 중에

"X좌표 차이와 Y좌표 차이 모두 1 이하일 경우로 정의된다"

이 조건을 보고

십자가 모양만 가능한 줄 알았다

대각선은 1.414.. 아닌가.. 했다

​

문제를 잘 읽어보니

두 좌표 차이 모두 1 이하일 경우 라면

x 도 1 이하 y 도 1 이하라

결국 8방향을 검사하는 것이였다.

​

그렇게 8방향으로 너비우선 탐색을 하고

또 봉오리로 체크된 거는 전역으로 체크해줘서

다시 검사 하지 않게 했다.

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

bool bongo[101][70];

pair<int, int> dir[] = { { -1, -1}, {-1,0},{-1,1},{0,-1},{0,1},
	{1,1},{1,0}, { 1,-1} };

bool check_in(int x, int y, int N, int M) {
	if (x >= N || x < 0 || y >= M || y < 0)
		return false;
	return true;
}

bool bfs(vector<vector<int>> mt, int N, int M,int row,int col) {

	queue<pair<int, int>> q;

	vector<vector<bool>> visit(N, vector<bool>(M, false));

	q.push(make_pair(row, col));
	int value = mt[row][col];
	int i, j;
	while (!q.empty()) {
		i = q.front().first;
		j = q.front().second;
		q.pop();

		if (visit[i][j])
			continue;
		visit[i][j] = true;
		bongo[i][j] = true;

		for (int k = 0; k < 8; k++) {
			int x = dir[k].first;
			int y = dir[k].second;

			if (check_in(i + x, j + y, N, M)) {
				if (mt[i + x][j + y] > value) {
					return false;
				}
				if (mt[i + x][j + y] == value) {
					q.push(make_pair(i + x, j + y));
				}
			}
		}

	}
	return true;
}



int main(void) {
	int N, M;
	cin >> N >> M;


	vector<vector<int>> mt(N, vector<int>(M));

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> mt[i][j];
		}
	}

	int ans = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if(!bongo[i][j])
				if (bfs(mt, N, M, i, j)) {
					ans++;
				}
		}
	}
	cout << ans;

}