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

发表于 更新于 分类于 本文字数： 756 阅读时长 ≈ 3 分钟

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

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

题面

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

输入

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

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

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

输出

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

样例输入和输出

Input

1
2
3
4
5
6
7
8
4 4
__O_
__O_
OO_O
__O_
1 1
O
0 0

Output

1
2
4
0

限制 2s/256M

思路

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

伪代码

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
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<<m_s<<endl;
    }
    return 0;
}