hdu 4090 GemAnd Prince

时间：2023-12-29 20:48:26

题目大意：

别人说是消消看，至于你玩没玩过。反正我是没玩过的。

就是选择一个钻石，可以消除与它相连的所有钻石。并获得 消除数量*消除数量  的分

思路：

直接暴搜，然后用一个cnt数组表示每一种钻石剩余的数量，进行剪枝。

被坑了两天。 开始用BFS 搜，用DFS进行标记。超内存。

后来改成了  DFS + DFS 发现有些细节不好处理。

最后换成了DFS搜  BFS标记消除。

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

int dx[] = {0,0,1,-1,1,1,-1,-1};

int dy[] = {1,-1,0,0,1,-1,-1,1};

int n,m,k;

int map[9][9];

int save[9][9][70];

bool vis[9][9][70];

int cnt[7];

int ans;

struct node

{

    int posx,posy;

}Q[1000];

bool ok(int x,int y)

{

    if(x>=1 && x<=n && y>=1 && y<=m)return true;

    return false;

}

void mtos(int dep)//存地图

{

    for(int i=1;i<=n;i++)

    for(int j=1;j<=m;j++)

    save[i][j][dep]=map[i][j];

}

void stom(int dep)

{

    for(int i=1;i<=n;i++)

    for(int j=1;j<=m;j++)

    map[i][j]=save[i][j][dep];

}

void reset(int top)//重新摆放

{

    for(int i=0;i<top;i++)//与后面的BFS 对应  消除。

    map[Q[i].posx][Q[i].posy]=0;

    int tmp[9][9];

    int ii,jj;

    for(int j=1;j<=m;j++)

    {

        ii=n;

        for(int i=n;i>=1;i--)

        {

            if(map[i][j]!=0)

            {

                jj=j;

                tmp[ii--][jj]=map[i][j];

            }

        }

        while(ii>=1)

        {

            tmp[ii][j]=0;

            ii--;

        }

    }

    int move[9],ccnt=0;

    memset(move,0,sizeof(move));

    for(int j=1;j<=m;j++)

    {

        if(tmp[n][j]==0)

        {

            move[j]=0;

            ccnt++;

            continue;

        }

        move[j]=ccnt;

    }

    for(int j=1;j<=m;j++)

    {

        for(int i=1;i<=n;i++)

        {

            tmp[i][j-move[j]]=tmp[i][j];

            if(move[j])tmp[i][j]=0;

        }

    }

    for(int i=1;i<=n;i++)

    for(int j=1;j<=m;j++)

    map[i][j]=tmp[i][j];

}

inline int h()//估价函数  剪枝

{

    int sum=0;

    for(int i=1;i<=k;i++)

    if(cnt[i]>=3)sum+=(cnt[i]*cnt[i]);

    return sum;

}

int mark(int x,int y,int val,int dep)//进行标记

{

    int head=0,tail=0;

    node w,e;

    Q[tail].posx=x;

    Q[tail++].posy=y;

    vis[x][y][dep]=true;

    while(head<tail)

    {

        w=Q[head];

        head++;

        for(int i=0;i<8;i++)

        {

            e=w;

            int xx=e.posx+dx[i];

            int yy=e.posy+dy[i];

            if(ok(xx,yy) && !vis[xx][yy][dep] && map[xx][yy]==val)

            {

                vis[xx][yy][dep]=true;

                e.posx=xx;

                e.posy=yy;

                Q[tail++]=e;

            }

        }

    }

    return tail;

}

void dfs(int tans,int dep)

{

    ans=max(ans,tans);

    if(h()+tans<=ans)return;

    for(int i=1;i<=n;i++)//这里不可少  没进入一次新的DFS  都要重置

    for(int j=1;j<=m;j++)

    vis[i][j][dep]=false;

    for(int i=1;i<=n;i++)

    {

        for(int j=1;j<=m;j++)

        {

            if(map[i][j]!=0 && !vis[i][j][dep])

            {

                int tscore=mark(i,j,map[i][j],dep);

                if(tscore>=3)

                {

                    mtos(dep);

                    int vv=map[i][j];//被这里坑了好久  RESET之后地图就会变了。无力吐槽自己

                    cnt[vv]-=tscore;

                    reset(tscore);

                    dfs(tans+tscore*tscore,dep+1);

                    cnt[vv]+=tscore;

                    stom(dep);

                }

            }

        }

    }

}

int main()

{

    while(scanf("%d%d%d",&n,&m,&k)!=EOF)

    {

        memset(cnt,0,sizeof(cnt));

        for(int i=1;i<=n;i++)

        for(int j=1;j<=m;j++)

        {

            scanf("%d",&map[i][j]);

            cnt[map[i][j]]++;

        }

        ans=0;

        memset(vis,false,sizeof(vis));

        dfs(0,1);

        printf("%d\n",ans);

    }

    return 0;

}

/*

8 8 6

1 1 1 2 2 2 3 3

4 4 1 1 4 4 4 4

5 5 5 6 6 6 6 1

2 2 2 2 4 4 4 3

1 4 5 6 3 3 2 1

4 4 4 5 5 5 5 6

5 5 5 5 5 3 3 3

5 5 2 2 2 1 3 1

*/

这里在给出DFS + DFS 的 AC代码。 效率没有上一个快，只是为了检验自己之前的错误。

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

int dx[] = {0,0,1,-1,1,1,-1,-1};

int dy[] = {1,-1,0,0,1,-1,-1,1};

int n,m,k;

int map[9][9];

int save[9][9][70];

bool vis[9][9][70];

int cnt[7];

int tscore;

int ans;

void debugcnt()

{

    for(int i=1;i<=k;i++)

    printf("%d ",cnt[i]);

    puts("");

    system("pause");

   // getchar();

}

bool ok(int x,int y)

{

    if(x>=1 && x<=n && y>=1 && y<=m)return true;

    return false;

}

void debug()

{

    for(int i=1;i<=n;i++)

    {

        for(int j=1;j<=m;j++)

        {

            printf("%d",map[i][j]);

        }

        puts("");

    }

    puts("");

    //getchar();

}

void mtos(int dep)

{

    for(int i=1;i<=n;i++)

    for(int j=1;j<=m;j++)

    {

        save[i][j][dep]=map[i][j];

    }

}

void stom(int dep)

{

    for(int i=1;i<=n;i++)

    for(int j=1;j<=m;j++)

    {

        map[i][j]=save[i][j][dep];

    }

}

void reset()

{

    int tmp[9][9];

    int ii,jj;

    for(int j=1;j<=m;j++)

    {

        ii=n;

        for(int i=n;i>=1;i--)

        {

            if(map[i][j]!=0)

            {

                jj=j;

                tmp[ii--][jj]=map[i][j];

            }

        }

        while(ii>=1)

        {

            tmp[ii][j]=0;

            ii--;

        }

    }

    int move[9],ccnt=0;

    memset(move,0,sizeof(move));

    for(int j=1;j<=m;j++)

    {

        if(tmp[n][j]==0)

        {

            move[j]=0;

            ccnt++;

            continue;

        }

        move[j]=ccnt;

    }

    for(int j=1;j<=m;j++)

    {

        for(int i=1;i<=n;i++)

        {

            tmp[i][j-move[j]]=tmp[i][j];

            if(move[j])tmp[i][j]=0;

        }

    }

    for(int i=1;i<=n;i++)

    for(int j=1;j<=m;j++)

    map[i][j]=tmp[i][j];

}

int h()

{

    int sum=0;

    for(int i=1;i<=k;i++)

    if(cnt[i]>=3)sum+=cnt[i]*cnt[i];

    return sum;

}

void mark(int x,int y,int val,int dep)

{

    for(int i=0;i<8;i++)

    {

        int xx=dx[i]+x;

        int yy=dy[i]+y;

        if(ok(xx,yy) && !vis[xx][yy][dep] && map[xx][yy]==val)

        {

            vis[xx][yy][dep]=true;

            map[xx][yy]=0;

            tscore++;

            mark(xx,yy,val,dep);

        }

    }

}

void dfs(int tans,int dep)

{

    if(tans+h()<=ans){return;}

    ans=max(ans,tans);

    for(int i=1;i<=n;i++)

    for(int j=1;j<=m;j++)

    vis[i][j][dep]=false;

    for(int i=1;i<=n;i++)

    {

        for(int j=1;j<=m;j++)

        {

            if(map[i][j]!=0 && !vis[i][j][dep])

            {

                mtos(dep);

                int tt;

                tscore=0;

                int vv=map[i][j];

                mark(i,j,map[i][j],dep);

                tt=tscore;

                if(tt<3){stom(dep);continue;}

                cnt[vv]-=tt;

                reset();

                dfs(tans+tt*tt,dep+1);

                cnt[vv]+=tt;

                stom(dep);

            }

        }

    }

}

int main()

{

    while(scanf("%d%d%d",&n,&m,&k)!=EOF)

    {

        memset(cnt,0,sizeof(cnt));

        for(int i=1;i<=n;i++)

        for(int j=1;j<=m;j++)

        {

            scanf("%d",&map[i][j]);

            cnt[map[i][j]]++;

        }

        ans=0;

        dfs(0,1);

        printf("%d\n",ans);

    }

    return 0;

}

再上一份自己之前超内存的BFS 的代码。

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <queue>

#include <cstring>

using namespace std;

int dx[] = {0,0,-1,1,1,1,-1,-1};

int dy[] = {1,-1,0,0,1,-1,1,-1};

int n,m,k;

struct node

{

    short map[9][9];

    int score;

};

bool vis[9][9];

bool v[9][9];

bool ok(int x,int y)

{

    if(x<=n && x>=1 && y>=1 && y<=m)return true;

    return false;

}

int tscore;

void dfs(int x,int y,node &t,int val)

{

    for(int i=0;i<8;i++)

    {

        int xx=dx[i]+x;

        int yy=dy[i]+y;

        if( ok(xx,yy) && !vis[xx][yy] && t.map[xx][yy]==val)

        {

            vis[xx][yy]=true;

            t.map[xx][yy]=0;

            tscore++;

            v[xx][yy]=true;

            dfs(xx,yy,t,val);

        }

    }

}

int h(node t)

{

    int tcnt[7];

    for(int i=1;i<=n;i++)

    {

        for(int j=1;j<=m;j++)

        {

            if(t.map[i][j]!=0)

            {

                tcnt[t.map[i][j]]++;

            }

        }

    }

    int sum=0;

    for(int i=1;i<=k;i++)

    if(tcnt[i]>=3)sum+=tcnt[i]*tcnt[i];

    return sum;

}

node reset(node t)

{

    node tmp=t;

    int ii,jj;

    for(int j=1;j<=m;j++)

    {

        ii=n;

        for(int i=n;i>=1;i--)

        {

            if(t.map[i][j]!=0)

            {

                jj=j;

                tmp.map[ii--][jj]=t.map[i][j];

            }

        }

        while(ii>=1)

        {

            tmp.map[ii][j]=0;

            ii--;

        }

    }

    //debug(tmp);

    int move[9],ccnt=0;

    memset(move,0,sizeof(move));

    for(int j=1;j<=m;j++)

    {

        if(tmp.map[n][j]==0)

        {

            move[j]=0;

            ccnt++;

            continue;

        }

        move[j]=ccnt;

    }

    for(int j=1;j<=m;j++)

    {

        for(int i=1;i<=n;i++)

        {

            tmp.map[i][j-move[j]]=tmp.map[i][j];

            if(move[j])tmp.map[i][j]=0;

        }

    }

    return tmp;

}

int ans;

void bfs(node t)

{

    queue<node>Q;

    node w,e;

    Q.push(t);

    while(!Q.empty())

    {

        w=Q.front();

        Q.pop();

        if(w.score>ans)

        {

            ans=w.score;

        }

        memset(v,false,sizeof(v));

        for(int i=1;i<=n;i++)

        {

            for(int j=1;j<=m;j++)

            {

                if(v[i][j])continue;

                if(w.map[i][j]!=0)

                {

                    e=w;

                    tscore=0;

                    memset(vis,false,sizeof(vis));

                    dfs(i,j,e,e.map[i][j]);

                    if(tscore>=3)

                    {

                        e=reset(e);

                        e.score+=(tscore*tscore);

                        if(e.score+h(e)<=ans)continue;

                        Q.push(e);

                    }

                }

            }

        }

    }

}

int main()

{

    while(scanf("%d%d%d",&n,&m,&k)!=EOF)

    {

        node t;

        for(int i=1;i<=n;i++)

        for(int j=1;j<=m;j++)

        {

            scanf("%d",&t.map[i][j]);

        }

        t.score=0;

        ans=0;

        bfs(t);

        printf("%d\n",ans);

    }

    return 0;

}

相关文章