个人题解，和比赛官方无关，仅供参考

2020工大杯题解 - A - I同学的课间

题面

I 同学的课间自然离不开家喻户晓门当户对怡情益智的小游戏消消乐，但是 I 同学很懒，聪明美丽善良大方机智勇敢勤劳可爱的你快来帮帮他，找到每一回合得分最大的走法吧！

输入

题目有多组输入数据（不超过 100 组），每组数据为消消乐某一回合棋盘。

第一行为空格分割的两个整数，分别代表消消乐游戏棋盘的行数和列数，当为时，代表多组数据结束，不做输出，否则保证。

接下来的行，每行为个非空字符。其中 O 代表黑色子，_ 代表白色子。每一回合，可以交换同一行或同一列中任意一对相邻棋子。如果交换后，在同一行或同一列当中出现连续三个或以上相同颜色的棋子，则这一步得分为上述相同颜色棋子的个数的最大值，否则得分为，棋盘恢复原状。

输出

对于每组数据，输出一行，包含一个整数，为该回合得分最大的一步的得分。

样例输入和输出

Input

4 4
__O_
__O_
OO_O
__O_
1 1
O
0 0

Output

4
0

限制 2s/256M

思路

首先进行时间复杂度分析。是，暴力算法的时间复杂度是 (枚举交换，求当前分数)，可以接受。因此，暴力枚举交换，计算当前分数即可。

伪代码

读入 n，m
如果 n，m 均为 0，退出
读入矩阵
枚举每个点：
    如果他右边有点，和右边交换后计算分数，如果分数超过历史最大值，保存分数。换回来。
    下边同理
输出最高分数。

代码

#include 
using namespace std;
#define MAXN 50
#define O 0
#define _ 1
int map[MAXN][MAXN] = {0};
int n,m;

int score(){ // 计算分数
    int m_c = 0;
    int last = -1;
    int last_count = 0;
    for(int i = 0; i < n; ++ i){
        last = -1;
        last_count = 0;
        for(int j = 0; j < m; ++ j){
            if (map[i][j] == last){
                last_count ++;
            } else {
                last_count = 1;
                last = map[i][j];
            }
            m_c = m_c > last_count ? m_c : last_count;
        }
    }
    for(int j = 0; j < m; ++ j){
        last = -1;
        last_count = 0;
        for(int i = 0; i < n; ++ i){
            if (map[i][j] == last){
                last_count ++;
            } else {
                last_count = 1;
                last = map[i][j];
            }
            m_c = m_c > last_count ? m_c : last_count;
        }
    }
    return m_c >= 3 ? m_c : 0;
}
void swap(int x1, int y1, int x2, int y2){ // 交换
    int t = map[x1][y1];
    map[x1][y1] = map[x2][y2];
    map[x2][y2] = t;
}

int main(){
    char c;
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m_s = 0;
    int c_s;
    while(cin>>n>>m, n!=0 && m!=0){
        m_s = 0;
        for(int i = 0; i < n; ++ i){
            for(int j = 0; j < m; ++ j){
                cin>>c;
                map[i][j] = c == '_' ? _ : O;
            }
        }
        for(int i = 0; i < n; ++ i){
            for(int j = 0; j < m; ++ j){
                if(i+1 < n){
                    swap(i,j,i+1,j);
                    c_s = score();
                    if(c_s > m_s){
                        m_s = c_s;
                    }
                    swap(i,j,i+1,j);
                }
                if(j+1 < m){
                    swap(i,j,i,j+1);
                    c_s = score();
                    if(c_s > m_s){
                        m_s = c_s;
                    }
                    swap(i,j,i,j+1);
                }
            }
        }
        cout<