[BOJ/Silver 1] 백준 29634 Hotel(C++)

문제 링크

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

 

문제

Pavel was dreaming to become an architect since his early childhood. He often drew plans of buildings on sheets of paper, and sometimes on tables and walls. Now he has a university degree and is a famous architect.

Once Pavel was digging in his child drawings and found an interesting plan of the hotel floor. The floor is a rectangle with size n×m meters. On the plan, each square corresponding to a square meter of the floor was painted with either blue or red color. After thinking a little, Pavel understood that the blue color is for corridors, and the red color stands for hotel rooms.

Since his childhood, Pavel tries to comply with international standards. Following the standards, a hotel room must be rectangular, so it should be represented on the plan as a rectangle filled with red color. Sides of the room should be parallel to the floor boundaries. Moreover, there is always a corridor running along each side of each hotel room.

In order to comply with the fire safety regulations, there should be corridors at the sides of the floor. So, the first and the last rows, as well as the first and the last columns of the plan are blue.

Looking at his plan, Pavel wondered, what is the maximal area of a hotel room on his plan. Write a program to find this area.

 

입력

The input file contains the description of Pavel's plan.

The first line of the input file contain two integers n and m (3 ≤ n, m ≤ 30). The following n lines contain m symbols each. The symbol "*" corresponds to a square filled with blue color (a square meter of a corridor), and the symbol "." is a red square --- a square meter of a room.

 

출력

In the first line of the output file print the area of the largest hotel room. If there are no rooms on the plan, print "-1".

 

예제 입력 1

5 5
*****
*.***
**..*
**..*
*****

예제 출력 1

4

예제 입력 2

4 5
*****
*.***
*.*.*
*****

예제 출력 2

2

예제 입력 3

3 3
***
***
***

예제 출력 3

-1

 

알고리즘 분류

• 그래프 탐색

 

풀이

BFS로 "."로만 이루어진 구역의 최대 칸 수를 구하면 된당.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 31
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M;
int MAP[MAX][MAX];
bool Visited[MAX][MAX];
int MoveY[4] = { -1,0,1,0 };
int MoveX[4] = { 0,-1,0,1 };
int Answer = -1;

void input() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		string S;
		cin >> S;
		for (int j = 0; j < M; j++) {
			if (S[j] == '.') {
				MAP[i][j] = 1;
			}
		}
	}
}

int bfs(int Y, int X) {
	queue<pair<int, int> > Q;
	Q.push(make_pair(Y, X));
	Visited[Y][X] = true;
	int Result = 0;

	while (!Q.empty()) {
		int NowY = Q.front().first;
		int NowX = Q.front().second;
		Q.pop();

		Result++;

		for (int i = 0; i < 4; i++) {
			int NextY = NowY + MoveY[i];
			int NextX = NowX + MoveX[i];
			if ((NextY >= 0) && (NextY < N) && (NextX >= 0) && (NextX < M) && !Visited[NextY][NextX] && (MAP[NextY][NextX] == 1)) {
				Q.push(make_pair(NextY, NextX));
				Visited[NextY][NextX] = true;
			}
		}
	};

	return Result;
}

void settings() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (!Visited[i][j] && (MAP[i][j] == 1)) {
				Answer = max(Answer, bfs(i, j));
			}
		}
	}
}

void find_Answer() {
	cout << Answer << "\n";
}

int main() {
	FASTIO
	input();
	settings();
	find_Answer();

	return 0;
}