NC16125. 不开心消消乐
描述
输入描述
输入一个8行8列的矩阵m,m[i][j]表示第i行，第j列的小球的种类编号。
输出描述
输出一个数，表示只任意交换一对相邻的小球后，最多能连续消去多少个小球。
示例1
输入:
1 7 2 4 6 3 2 1 7 1 3 4 6 2 3 2 1 4 4 1 8 3 2 3 6 6 2 1 7 7 4 4 3 3 1 2 3 3 7 5 4 7 2 1 8 4 8 6 8 6 2 1 3 4 5 7 1 2 3 4 5 6 7 8
输出:
16
示例2
输入:
5 5 4 6 5 8 2 8 8 3 8 7 2 5 1 2 3 1 3 1 8 8 4 4 4 6 1 5 3 4 2 8 7 1 2 2 7 6 6 8 4 2 4 2 6 4 6 7 7 7 3 5 3 5 7 6 1 7 7 8 7 1 2 7
输出:
6
C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 488K, 提交时间: 2018-06-02 12:48:46
#include<map>
#include<cstdio>
#include<algorithm>
using namespace std;
int mx,mp[10][10],h[10][10],ans[10][10];
/*
1 7 2 4 6 3 2 1
7 1 3 4 6 2 3 2
1 4 4 1 8 3 2 3
6 6 2 1 7 7 4 4
3 3 1 2 3 3 7 5
4 7 2 1 8 4 8 6
8 6 2 1 3 4 5 7
1 2 3 4 5 6 7 8*/
int J(){
bool f=0;
for(int i=1;i<=8;++i) for(int j=1;j<=8;++j) h[i][j]=ans[i][j];
while(1){
f=0;
for(int i=1;i<=8&&!f;++i) {
int k,num;
for(int j=1;j<=8&&!f;j=k) {
k=j+1,num=h[i][j];
int cnt=1;
for(;k<=8;++k) if(!h[i][k]) continue;
else if(h[i][k]==num) ++cnt;
else break;
if(cnt>=3) for(int l=j;l<k;++l) h[i][l]=0;
if(cnt>=3) f=1;
}
}
for(int i=1;i<=8&&!f;++i) {
int k,num;
for(int j=1;j<=8&&!f;j=k){
k=j+1,num=h[j][i];
int cnt=1;
for(;k<=8;++k) if(!h[k][i]) continue;
else if(h[k][i]==num) ++cnt;
else break;
if(cnt>=3) for(int l=j;l<k;++l) h[l][i]=0;
if(cnt>=3) f=1;
}
}
if(!f) {
int ret=0;
for(int i=1;i<=8;++i) for(int j=1;j<=8;++j) if(!h[i][j]) ++ret;
mx=max(mx,ret);
return 0;
}
}
}
int main(){
for(int i=1;i<=8;++i) for(int j=1;j<=8;++j) scanf("%d",&mp[i][j]),ans[i][j]=mp[i][j];
for(int i=1;i<=8;++i) for(int j=1;j<8;++j) {
swap(ans[i][j],ans[i][j+1]);
J();
swap(ans[i][j],ans[i][j+1]);
}
for(int i=1;i<8;++i) for(int j=1;j<=8;++j) {
swap(ans[i][j],ans[i+1][j]);
J();
swap(ans[i][j],ans[i+1][j]);
}
printf("%d\n",mx);
}
C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 380K, 提交时间: 2020-08-18 18:20:28
#include<map>
#include<cstdio>
#include<algorithm>
using namespace std;
int mx,mp[10][10],h[10][10],ans[10][10];
int J(){
bool f=0;
for(int i=1;i<=8;++i) for(int j=1;j<=8;++j) h[i][j]=ans[i][j];
while(1){
f=0;
for(int i=1;i<=8&&!f;++i) {
int k,num;
for(int j=1;j<=8&&!f;j=k) {
k=j+1,num=h[i][j];
int cnt=1;
for(;k<=8;++k) if(!h[i][k]) continue;
else if(h[i][k]==num) ++cnt;
else break;
if(cnt>=3) for(int l=j;l<k;++l) h[i][l]=0;
if(cnt>=3) f=1;
}
}
for(int i=1;i<=8&&!f;++i) {
int k,num;
for(int j=1;j<=8&&!f;j=k){
k=j+1,num=h[j][i];
int cnt=1;
for(;k<=8;++k) if(!h[k][i]) continue;
else if(h[k][i]==num) ++cnt;
else break;
if(cnt>=3) for(int l=j;l<k;++l) h[l][i]=0;
if(cnt>=3) f=1;
}
}
if(!f) {
int ret=0;
for(int i=1;i<=8;++i) for(int j=1;j<=8;++j) if(!h[i][j]) ret++;
mx=max(mx,ret);
return 0;
}
}
}
int main(){
for(int i=1;i<=8;++i) for(int j=1;j<=8;++j) scanf("%d",&mp[i][j]),ans[i][j]=mp[i][j];
for(int i=1;i<=8;++i) for(int j=1;j<8;++j) {
swap(ans[i][j],ans[i][j+1]);
J();
swap(ans[i][j],ans[i][j+1]);
}
for(int i=1;i<8;++i) for(int j=1;j<=8;++j) {
swap(ans[i][j],ans[i+1][j]);
J();
swap(ans[i][j],ans[i+1][j]);
}
printf("%d\n",mx);
}