hdu 2259

hdu 2259"/>

hdu 2259

题目：.php?pid=2259

题意是找一种策略，可以使这个策略得到值比continuous same game(1) 的策略好1.5倍就可以了。也其实就是不用找最优的策略。。只要稍微比（1）的策略好就行。。。。

我一开始往找最优策略方向了。所以一直超时。。最后被我水过了。

下面是AC代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<queue>
using namespace std;
#define maxn 21
char map[maxn][maxn];
bool vis[maxn][maxn];
bool mark[maxn][maxn];
int n,m;
int greedans;
int dir[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};
inline bool cheack(int x,int y){   return x>=0&&x<n&&y>=0&&y<m;  }
void dfs(int x,int y,char color,int &num,char temp_map[maxn][maxn])
{for(int i=0; i<4; i++){int nx=x+dir[i][0],ny=y+dir[i][1];if(cheack(nx,ny)&&!vis[nx][ny]&&temp_map[nx][ny]==color){vis[nx][ny]=true;temp_map[nx][ny]='0';num+=1;dfs(nx,ny,color,num,temp_map);}}
}void move_zero(char map[maxn][maxn])
{vector<char > temp[maxn];int len=0,i,j;for( i=0; i<m; i++){for( j=n-1; j>=0; j--)if(map[j][i]>'0') break;if(j>=0){for(int j=n-1; j>=0; j--){if(map[j][i]>'0')temp[len].push_back(map[j][i]);}for(int j=temp[i].size(); j<n; j++)temp[len].push_back('0');len++;}}for(int i=len; i<m; i++){for(int j=0; j<n; j++)temp[i].push_back('0');}for(int i=0; i<n; i++)for(int j=0; j<m; j++){map[i][j]=temp[j][n-1-i];}
}
struct node{int ans,val,step,s,color[210];int cnt[maxn][maxn];char map[maxn][maxn];int x[30],y[30];bool operator < (const node &a)  const{return val<a.val;}
}s_pos,ans;
void f(node &next){                                //求剩余连通块,并评估char t[maxn][maxn];for(int i=0;i<n;i++) for(int j=0;j<m;j++) {t[i][j]=next.map[i][j];nextt[i][j]=0;}memset(vis,false,sizeof(vis));next.s=0;for(int i=0;i<n;i++) for(int j=0;j<m;j++){if(!vis[i][j]&&t[i][j]>'0'){int res=1;  char c=t[i][j];vis[i][j]=true;dfs(i,j,c,res,t);if(res>1){next.color[++next.s]=res;nextt[i][j]=1;}}}next.val=next.ans;for(int i=1;i<=next.s;i++) next.val+=(next.color[i]*(next.color[i]-1));
}
void bfs(){int cnt=0;priority_queue<node > q;q.push(s_pos);while(!q.empty()){node now = q.top();  q.pop();if(now.ans>ans.ans) {ans=now; }if(++cnt>=25) break;for(int i=0;i<n;i++) for(int j=0;j<m;j++){char c = now.map[i][j];int is=nowt[i][j];if((c-'0')>0&&is){node next = now;next.map[i][j]='0';next.x[next.step]=i;  next.y[next.step]=j; next.step++;int t_val=1;memset(vis,false,sizeof(vis));  vis[i][j]=true;dfs(i,j,c,t_val,next.map);if(t_val==1) continue;next.ans+=t_val*(t_val-1);next.color[c-'0']-=t_val;move_zero(next.map);f(next);q.push(next);}}}printf("%d\n",ans.step);for(int i=0;i<ans.step;i++)printf("%d %d\n",ans.x[i],ans.y[i]);
}
void solve(){memset(s_pos.color,0,sizeof(s_pos.color));s_pos.ans=s_pos.val=ans.ans=greedans=s_pos.step=0;s_pos.s=0;for(int i=0;i<n;i++) for(int j=0;j<m;j++){s_pos.color[map[i][j]-'0']++;    s_pos.map[i][j]=map[i][j];}f(s_pos);bfs();
}
int main()
{while(scanf("%d%d",&n,&m)!=EOF){for(int i=0; i<n; i++)  scanf("%s",map[i]);solve();}return 0;
}