0%

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

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

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<

欢迎关注我的其它发布渠道