P7749 [COCI2013-2014#2] MISA 题解

· · 题解

P7749 [COCI2013-2014#2] MISA 题解

思路：先求出 Mirko 没入座时人们的握手次数，再枚举 Mirko 入座的位置，若这个座位为空，那么计算 Mirko 在这个位置入座的握手次数，求出最大值。否则跳过。最后输出 Mirko 可以握手的最大次数加上 Mirko 没入座的所有人的握手次数。

对于刚开始 Mirko 没入座时所有人的握手次数，可以把每个人的的握手次数相加，最后除以 2 。因为握手时双向的，计算过程中，每一次握手都被计算了两次，所以最后要除以 2 。

还有两个小优化：

  1. 若会场坐满了，可以直接输出，不用枚举 Mirko 入座的位置，因为他无处可坐了。
  2. 如果枚举到某一时刻， Mirko 可以握手的人数为 8 ，可直接输出答案，因为一个人最多与周围八个人握手。

Code：

#include <stdio.h>
#define clac(r, c) (flag[r - 1][c - 1] + flag[r - 1][c] + flag[r - 1][c + 1] + flag[r][c - 1] + flag[r][c + 1] + flag[r + 1][c - 1] + flag[r + 1][c] + flag[r + 1][c + 1])//计算握手的人数 
#define max(a, b) ((a) > (b) ? (a) : (b))//手写max函数 
bool bol = true, flag[64][64];
int n, m, sum, ans;
char ch[64][64];
int main() {
    scanf("%d%d", &n, &m);
    getchar();
    for(int i = 1; i <= n; ++i) scanf("%s", ch[i] + 1);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            bol &= flag[i][j] = (ch[i][j] == 'o');//其实这里这样写是为了偷懒，可以写成flag[i][j] = (ch[i][j] == 'o'); if(!flag[i][j]) bol = false;
    //计算Mirko没入座时人们的握手情况
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            if(flag[i][j]) sum += clac(i, j);
    sum /= 2;
    if(bol) return 0 * printf("%d", sum);//第一种优化 
    //枚举Mirko的位置
   for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j) {
            if(!flag[i][j]) ans = max(ans, clac(i, j));//i行j列位置Mirko的握手次数
            if(ans == 8) return 0 * printf("%d", sum + ans);//第二种优化 
        }
    printf("%d", sum + ans);
    return 0;
}