알고리즘
백준 9518번 로마 카톨릭 미사 C++
영춘권의달인
2023. 4. 4. 17:00
https://www.acmicpc.net/problem/9518
9518번: 로마 카톨릭 미사
로마 카톨릭 미사에서 가장 멋진 부분은 사람들이 서로 악수를 하면서 "평화가 함께하기를" 이라고 말하는 평화 의식이다. 성당에는 R개의 벤치가 한 행에 하나씩 있고, 각 벤치에는 총 S명이 앉
www.acmicpc.net
빈 자리에 하나씩 배치하면서 악수한 횟수를 구했다. 그리고 1번과 2번이 악수한것과 2번과 1번이 악수한것은 같기 때문에 구한 횟수에서 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 <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>
using namespace std;
using int64 = long long;
int dRow[8] = { -1,-1, 0, 1, 1, 1, 0,-1 };
int dCol[8] = { 0, 1, 1, 1, 0,-1,-1,-1 };
int r, s;
vector<vector<bool>> filled;
vector<pair<int, int>> sg;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> r >> s;
filled = vector<vector<bool>>(r, vector<bool>(s, false));
for (int i = 0; i < r; i++) {
string str;
cin >> str;
for (int j = 0; j < s; j++) {
if (str[j] == 'o') filled[i][j] = true;
else sg.push_back({ i,j });
}
}
if (sg.empty()) sg.push_back({ 0,0 });
int ans = 0;
for (auto curr : sg) {
filled[curr.first][curr.second] = true;
set<pair<int,int>> handShakes;
int cnt = 0;
for (int i = 0; i < r; i++) {
for (int j = 0; j < s; j++) {
if (filled[i][j] == false) continue;
for (int k = 0; k < 8; k++) {
int nextRow = i + dRow[k];
int nextCol = j + dCol[k];
if (nextRow < 0 || nextRow >= r) continue;
if (nextCol < 0 || nextCol >= s) continue;
if (filled[nextRow][nextCol] == false) continue;
cnt++;
}
}
}
ans = max(ans, cnt / 2);
filled[curr.first][curr.second] = false;
}
cout << ans;
}