学步园

题目：http://acm.hdu.edu.cn/showproblem.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];next.cnt[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;
                  next.cnt[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=now.cnt[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;
}