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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
| #include <stdio.h>
#include <string.h>
int m, n, k, max, hash[7], mat[8][8], tmat[8][8], dir[3]= {-1,0,1};
struct Point
{
int x, y;
inline void set(int a, int b)
{
x = a, y = b;
}
};
int evaluate()//估值函数
{
int eval = 0;
for(int i = 1; i <= k; ++ i)
eval += hash[i] * hash[i];
return eval;
}
void modify()//方块的左移和掉落
{
int head;
for(int i = 0; i < m; ++ i)
{
head = n - 1;
while(head >= 0)
{
if(mat[head][i] == 0) break;
else -- head;
}
if(head > 0)
{
for(int j = head - 1; j >= 0; -- j)
if(mat[j][i] != 0)
{
mat[head--][i] = mat[j][i];
mat[j][i] = 0;
}
}
}
bool zerocol;
for(head = 0; head < m ; ++ head)
{
zerocol = true;
for(int i = 0; i < n; ++ i)
if(mat[i][head] != 0) zerocol = false;
if(zerocol) break;
}
if(head < m - 1)
{
for(int i = head + 1; i < m; ++ i)
{
zerocol = true;
for(int j = 0; j < n; ++ j)
if(mat[j][i] != 0) zerocol = false;
if(!zerocol)
{
for(int j = 0; j < n; ++ j)
{
mat[j][head] = mat[j][i];
mat[j][i] = 0;
}
++ head;
}
}
}
}
int travese(int x, int y, int mat[8][8], int val)//在mat上将和(x,y)点值相同且(x,y)连通的点标记成val
{
Point queue[64], tmp;
int head = 0, tail = 0, v = mat[x][y];
queue[tail++].set(x,y);
mat[x][y] = val;
while(head < tail)
{
tmp = queue[head++];
for(int i = 0; i < 3; ++ i)
for(int j = 0; j < 3; ++ j)
{
if(mat[tmp.x + dir[i]][tmp.y + dir[j]] == v && tmp.x + dir[i] >= 0 && tmp.x + dir[i] < n && tmp.y + dir[j] >= 0 && tmp.y + dir[j] < m)
{
mat[tmp.x + dir[i]][tmp.y + dir[j]] = val;
queue[tail++].set(tmp.x + dir[i] , tmp.y + dir[j]);
}
}
}
return tail;
}
int link(Point * p)
{
memcpy(tmat, mat, sizeof(tmat));
int cnt = 0;
for(int i = 0; i < n; ++ i)
for(int j = 0; j < m; ++ j)
{
if(tmat[i][j] > 0)
{
if(travese(i,j,tmat,-1)>= 3)
p[cnt++].set(i,j);
}
}
return cnt;
}
void dfs(int score)//暴力搜索
{
Point pnt[21];
int cnt = link(pnt);
if(cnt == 0)
max = max > score ? max : score;
else
{
int ta[8][8];
for(int i = 0; i < cnt; ++ i)
{
memcpy(ta, mat, sizeof(ta));
int t = travese(pnt[i].x, pnt[i].y, mat, 0);
hash[ta[pnt[i].x][pnt[i].y]]-= t;
if(evaluate() + score + t * t > max)//估值函数
{
modify();
dfs(score+ t * t);
}
hash[ta[pnt[i].x][pnt[i].y]]+= t;
memcpy(mat, ta, sizeof(ta));
}
}
}
int main()
{
while(scanf("%d%d%d", &n, &m , & k) != EOF)
{
memset(hash,0,sizeof(hash));
for(int i = 0; i < n; ++ i)
for(int j = 0; j < m; ++ j)
{
scanf("%d", mat[i]+j);
++hash[mat[i][j]];
}
max = 0;
dfs(0);
printf("%d\n",max);
}
return 0;
} |
