백준 9518번 로마 카톨릭 미사 C++

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

9518번: 로마 카톨릭 미사

 

빈 자리에 하나씩 배치하면서 악수한 횟수를 구했다. 그리고 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;
}