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

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

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;
}