DFS算,五分钟如果答案没有更新,那个解一般来说就很优了。

#include <cstdio>
#include <iostream>
#include <string.h>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>
#include <map>
#include <stack>
using namespace std;
int const uu[4] = {1,-1,0,0};
int const vv[4] = {0,0,1,-1};
typedef long long ll;
int const inf = 0x3f3f3f3f;
ll const INF = 0x7fffffffffffffffll;
double eps = 1e-10;
double pi = acos(-1.0);
#define rep(i,s,n) for(int i=(s);i<=(n);++i)
#define rep2(i,s,n) for(int i=(s);i>=(n);--i)
#define mem(v,n) memset(v,(n),sizeof(v))
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
struct node{
int x,y;
}tempAns[205],Ans[205]; char FIRST[101][101];
bool VIS[101][101];
int bestScore;
int STEP; bool check(char mp[101][101],int x,int y){
rep(k,0,3){
int xx=x+uu[k], yy=y+vv[k];
if(xx>=1&&xx<=100 && yy>=1&&yy<=100 && mp[xx][yy]==mp[x][y]) return true;
}
return false;
}
int color1(char mp[101][101],bool vis[101][101],int x,int y){
vis[x][y]=true;
int res=1;
rep(k,0,3){
int xx=x+uu[k], yy=y+vv[k];
if(xx>=1&&xx<=100 && yy>=1&&yy<=100 && vis[xx][yy]==false && mp[xx][yy]==mp[x][y]) res+=color1(mp,vis,xx,yy);
}
mp[x][y]=0;
return res;
}
void proc1(char mp[101][101]){
rep(j,1,10) rep2(i,9,1){
int g=i,h=j;
while(g+1<=10 && mp[g+1][h]==0) ++g;
mp[g][h]=mp[i][j];
if(g!=i) mp[i][j]=0;
}
rep(j,2,10){
if(mp[10][j]==0) continue;
int k;
for(k=j-1;k>=1;--k) if(mp[10][k]!=0) break;
if(k+1<j){
rep(i,1,10){
mp[i][k+1]=mp[i][j];
mp[i][j]=0;
}
}
}
} void print(){
char ms[101][101];
bool vs[101][101]; mem(vs,false);
rep(i,1,10) rep(j,1,10) ms[i][j]=FIRST[i][j];
rep(i,1,10){
rep(j,1,10)
if(Ans[1].x==i&&Ans[1].y==j)
printf("#");
else{
if(ms[i][j]==0)
printf(" ");
else
printf("%d",ms[i][j]);
}
cout<<endl;
}
rep(i,1,STEP){
printf("step%d = (%d,%d)\n",i,Ans[i].x,Ans[i].y); cout<<endl<<endl;
color1(ms,vs,Ans[i].x,Ans[i].y);
proc1(ms);
if(i!=STEP){
rep(k,1,10){
rep(j,1,10)
if(Ans[i+1].x==k&&Ans[i+1].y==j)
printf("#");
else{
if(ms[k][j]==0)
printf(" ");
else
printf("%d",ms[k][j]);
}
cout<<endl;
}
}
}
} //mp[][]:current state step:current step score:current score
void dfs(char mp[101][101],bool vis[101][101],int tx,int ty,int step,int score){
//printf("step=%d score=%d click on (%d,%d) of last image.\n",step,score,tx,ty);
/*rep(i,1,10){
rep(j,1,10) if(mp[i][j]!=0) printf("%d ",mp[i][j]); else printf(" ");
cout<<endl;
}*/
tempAns[step].x=tx;
tempAns[step].y=ty;
rep(i,1,10) rep(j,1,10){
if(mp[i][j]==0) continue; //这个位置是空的,跳过
if(vis[i][j]) continue; //计算过,跳过
if(check(mp,i,j)==false){ //点击这个位置没法消去块
vis[i][j]=true;
continue;
}
char temp_mp[101][101];
bool temp_vis[101][101]; mem(temp_vis,false);
rep(i1,1,10) rep(j1,1,10) temp_mp[i1][j1]=mp[i1][j1];
int ts=color1(temp_mp,vis,i,j);
proc1(temp_mp);
dfs(temp_mp,temp_vis,i,j,step+1,score+5*ts*ts);
}
if(score>bestScore){
STEP=step;
rep(i,0,step) Ans[i]=tempAns[i];
bestScore=score;
cout<<"bestScore = "<<bestScore<<endl;
//print();
rep(i,1,step) printf("step%d = (%d,%d)\n",i,Ans[i].x,Ans[i].y); cout<<endl<<endl;
}
} void read(){
rep(i,0,10) rep(j,0,10) FIRST[i][j]=-1;
freopen("c:\\hello.in","r",stdin);
rep(i,1,10) rep(j,1,10) scanf("%d",&FIRST[i][j]);
fclose(stdin);
}
void init(){
bestScore=0;
mem(VIS,false);
}
int main(){
read();
init();
dfs(FIRST,VIS,-1,-1,0,0);
}

最新文章

  1. 在C#中如何使用资源的方法
  2. laravel中如何写验证码文件,并防止中文乱码.
  3. Android复习指南
  4. velocity插件 veloeclipse 支持eclipse4.4
  5. MyEclipse导入ant项目——Java编程思想
  6. makefile--Unfound symbol
  7. ViewFilpper
  8. action中list传到JSP中取不到值的问题
  9. asp读取指定目录下的文件名
  10. redis学习笔记(14)---redis基本命令总结
  11. ABB中断设定
  12. CXF-01: WebService的第一个例子
  13. CTF丨2019互联网安全城市巡回赛&#183;西安站,我们来了!
  14. [JavaScript] audio在浏览器中自动播放
  15. 他将Yahoo!Hadoop从20个节点扩展为42000个节点
  16. 20165313 《Java程序设计》第二周学习总结
  17. 什么是PAGELATCH和PAGEIOLATCH
  18. java字符串利用dom4j转 xml 且遍历
  19. linux查看网卡驱动
  20. python IPv6 十进制和十六进制互转

热门文章

  1. 猪齿鱼 SaaS 版效能平台发布
  2. 关于PHP数组Key的强制类型转换
  3. Docker系列(14)- Portainer可视化面板安装
  4. 解决navicat 导出excel数字为科学计数法问题
  5. 超详细unittest单元测试框架总结
  6. php 扫描url死链接
  7. P4180-[BJWC2010]严格次小生成树【Kruskal,倍增】
  8. ASP.NET Core 中间件的使用(三):全局异常处理机制
  9. shiro的使用与JWT整合
  10. 域名系统-DNS