首页 > 搜索 > DFS搜索 > HDU 4090-GemAnd Prince-DFS-[解题报告]HOJ
2015
04-16

HDU 4090-GemAnd Prince-DFS-[解题报告]HOJ

GemAnd Prince

问题描述 :

Nowadays princess Claire wants one more guard and posts the ads throughout the kingdom. For her unparalleled beauty, generality, goodness and other virtues, many people gather at the capital and apply for the position. Because princess Claire is very clever, she doesn’t want a fool to be her guard. As Claire is clever, she invents a game to test the applicants. The game is described as follows.
The game begins with a rectangular board of n rows and m columns, containing n*m grids. Each grid is filled with a gem and each gem is covered by one color, denoted by a number.(as the following shows).
Activation

Activation

Activation

Activation

If a gem has the same color with another one, and shares the same corner or the same border with it, the two are considered to be adjacent. Two adjacent gems are said to be connective. And we define that if A and B are connective, B and C are connective, then A and C are connective, namely the adjacency is transitive. Each time we can choose a gem and pick up all of the gems connected to it, including itself, and get a score equal to the square of the number of the gems we pick this time(but to make the game more challenging, the number of gems to be picked each time must be equal or larger than three).Another rule is that if one gem is picked, all the gems above it(if there is any)fall down to fill its grid,and if there is one column containing no gems at all, all the columns at its right(also if there is any) move left to fill the column. These rules can be shown as follows.

Activation

As the picture [a] above,all the gems that has color 1 are connective. After we choose one of them to be picked, all the gems that are connected to it must also be picked together, as the picture [b] shows (here we use 0 to denote the holes generated by the absence of gems).
Then the rest gems fall, as shown in picture [c]. Then the rest gems move left, as shown in picture [d]. Because we picked six gems at this time, our score increases 6*6=36.And furthermore, because we cannot find another gem, which has at least three gems connected to it(including itself),to be picked, the game comes to an end.
Each applicant will face such a board and the one who gets the highest score will have the honor to serve princess Claire.
Aswmtjdsj also wants to serve for princess Claire. But he realizes that competing with so many people, even among whom there are powerful ACMers, apparently there is little chance to succeed. With the strong desire to be the lucky dog, Aswmtjdsj asks you for help. Can you help make his dream come true?

输入:

There are no more than 15 test cases, separated by a blank line, end with EOF. Each case has n+1 lines, the first line of a case has three integers n, m, k (1<=n, m<=8, 1<=k<=6). Each of the next n lines contains m integers. The integer at (i+1)th line and jth column denotes the color of the gem at the grid (i, j), where the grid(1, 1) denotes the top left one, while the grid(n, m) is the lower right one. The integer in the grid is among [1, k].

输出:

There are no more than 15 test cases, separated by a blank line, end with EOF. Each case has n+1 lines, the first line of a case has three integers n, m, k (1<=n, m<=8, 1<=k<=6). Each of the next n lines contains m integers. The integer at (i+1)th line and jth column denotes the color of the gem at the grid (i, j), where the grid(1, 1) denotes the top left one, while the grid(n, m) is the lower right one. The integer in the grid is among [1, k].

样例输入:

3 3 3
1 1 3
1 2 1
1 1 2

5 4 3
2 2 3 3
1 1 3 3
3 2 2 2
3 1 1 1
3 1 2 2

样例输出:

36
103

思路,dfs搜索,最优性剪枝。

个人被坑很久的地方就是枚举格子的时候,应该是枚举整个八连快,不然的话一定超时。

代码有点丑,将就一下吧。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
#include<map>
#include<string>
using namespace std;
int a[10][10];
int n,m,k;
int sum;
int ans;
int cnt[10];
int dx[]={-1,-1,-1,0,0,1,1,1};
int dy[]={-1,0,1,-1,1,-1,0,1};
struct node
{
    int x,y;
}Q[10000];
int top;
int isok(int x,int y,int use[][10])
{
    top=0;
    node t,f;
    int front=0,rear=0;
    f.x=x;f.y=y;
    Q[rear++]=f;
    use[x][y]=1;
    while(front<rear)
    {
        f=Q[front++];
        for(int d=0;d<8;d++)
        {
            t=f;
            t.x+=dx[d];
            t.y+=dy[d];
            if(a[t.x][t.y]==a[x][y]&&!use[t.x][t.y])
            {
               use[t.x][t.y]=1;
               Q[rear++]=t;
            }
        }
    }
    top=rear;
    return rear;
}
inline void save(int sa[][10])
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            sa[i][j]=a[i][j];
}
inline void read(int sa[][10])
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            a[i][j]=sa[i][j];
}
void debug()
{
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            cout<<a[i][j];
            cout<<endl;
    }
    system("pause");
}
void trans()
{
    for(int i=0;i<top;i++)
        a[Q[i].x][Q[i].y]=0;
    for(int i=1;i<=n-1;i++)
        for(int j=1;j<=m;j++)
        {
            int x=i,y=j;
            if(a[i][j]&&!a[i+1][j])
            {
                while(a[x][y])
                {
                    a[x+1][y]=a[x][y];
                    x--;
                }
                a[x+1][y]=0;
            }
        }
    for(int j=m;j>=1;j--)
    {
        int ok=1;
        for(int i=1;i<=n;i++)
            if(a[i][j]) ok=0;
        if(ok)
        {
            int p,k;
            for(int q=1;q<=n;q++)
            {
                for(p=m;p>j;p--)
                    if(a[q][p]) break;
                if(p==j) continue;
                for(k=j;k<p;k++)
                    a[q][k]=a[q][k+1];
                a[q][k]=0;
            }
        }
    }
}
inline int h()
{
    int tot=0;
    for(int i=1;i<=k;i++)
    {
        if(cnt[i]>=3) tot+=cnt[i]*cnt[i];
    }
    return tot;
}
void dfs(int score)
{
    ans=max(ans,score);
    if(h()+score<=ans) return;
    int tmp;
    int use[10][10]={0};
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]==0&&!use[i][j]) continue;
            tmp=isok(i,j,use);
            if(tmp>=3)
            {
                int sa[10][10];
                cnt[a[i][j]]-=tmp;
                save(sa);
                trans();
                dfs(score+tmp*tmp);
                read(sa);
                cnt[a[i][j]]+=tmp;
            }
        }
}
int main()
{
    while(scanf("%d%d%d",&n,&m,&k)!=EOF)
    {
        sum=0;
        memset(a,0,sizeof(a));
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%d",&a[i][j]);
                cnt[a[i][j]]++;
            }
        }
        ans=0;
        dfs(0);
        printf("%d\n",ans);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/t1019256391/article/details/10419555


, ,
  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  3. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。