[9518] 로마 카톨릭 미사

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

R*S의 배열이 주어진다.

배열은 이미 좌석 주인이 있으면 o 빈자리이면 . 로 정보로 준다.

상근이가 가장 마지막에 자리에 앉을 때 (빈자리 중에서 한자리)

사람들이 가장 많은 악수를 할 수 있는 횟수를 구하는 문제이다.

문제 해결 방안은 상근이를 빈자리에 한 번씩 앉혀본 후 8방향을 확인해봐서 o인 좌석의 개수를 세면 된다.

다만 문제에 함정이 몇 가지 있다.

첫째로 상근이의 악수 횟수를 구하는 문제가 아니라 모든 사람의 악수 횟수를 구하는 문제이다.

둘째로 빈자리가 없는 예도 있다.

첫 번째 함정은 간단하다. 그냥 악수 횟수를 상근이의 악수 횟수만 구하는게 아니라 모든 사람의 악수 횟수를 구한 뒤 

마지막 결과 값에 나누기 2 를 해주면 된다. 나누기 2를 해주는 이유는 모든 사람의 악수 횟수를 구하면 중복이 한 번씩 되기 때문이다.

두번째 함정은 문제를 어떻게 푸냐에 따라 함정이 아닐 수도 있는데 나에겐 함정이었다.

이 경우는 그냥 예외처리를 해주었다.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
//상 하 좌 우 상좌 상우 하좌 하우
int dx[8] = { 0, 0, -1, 1, -1, 1, -1, 1 };
int dy[8] = { 1, -1, 0, 0, 1, 1, -1, -1 };
int arr[55][55];
int n, m, maxi, cnt;
bool flag;
void func(int x, int y) {
    for (int i = 0; i<8; i++) {
        int nx = dx[i] + x;
        int ny = dy[i] + y;
        if (nx < 0 || nx >= n || ny < 0 || ny >= m || arr[nx][ny] == 0) continue;
        cnt++;
    }
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i<n; i++) {
        for (int j = 0; j<m; j++) {
            char a;
            scanf(" %1c", &a);
            if (a == 'o')
                arr[i][j] = 1;
            else
                flag = 1;
        }
    }
    if (!flag) {
        for (int k = 0; k<n; k++) {
            for (int l = 0; l<m; l++) {
                func(k, l);
            }
        }
        printf("%d\n", cnt/2);
        return 0;
    }
 
    for (int i = 0; i<n; i++) {
        for (int j = 0; j<m; j++) {
            if (arr[i][j] == 0) {
                arr[i][j] = 1;
                for (int k = 0; k<n; k++) {
                    for (int l = 0; l<m; l++) {
                        if (arr[k][l] == 1) {
                            func(k, l);
                        }
                    }
                }
                maxi = max(maxi, cnt);
                arr[i][j] = 0;
                cnt = 0;
            }
        }
    }
 
    printf("%d\n", maxi/2);
 
    return 0;
}