hdu 4090--GemAnd Prince(搜索)
2018-06-17 21:50:33来源:未知 阅读 ()
题目链接
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).
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.
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?
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> //#include <windows.h> using namespace std; struct Node { int a[9][9]; }; int n,m,k; int dx[8]={1,1,1,0,0,-1,-1,-1}; int dy[8]={1,0,-1,1,-1,1,0,-1}; int ans; /**void print(Node s) { for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) cout<<s.a[i][j]<<" "; cout<<endl; } }*/ int get(Node s) { int r[10]; for(int i=1;i<=k;i++) r[i]=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) r[s.a[i][j]]++; } int ans=0; for(int i=1;i<=k;i++) ans+=r[i]*r[i]; return ans; } int dfs(Node &t,int x,int y,int d,Node &p) { int num=1; t.a[x][y]=0; p.a[x][y]=0; for(int i=0;i<8;i++) { int nx=x+dx[i]; int ny=y+dy[i]; if(nx<1||nx>n||ny<1||ny>m||t.a[nx][ny]!=d) continue; num+=dfs(t,nx,ny,d,p); } return num; } void change1(Node &t) { for(int i=1;i<=m;i++) { int pos=n; for(int j=n;j>=1;j--) { if(t.a[j][i]==0) continue; t.a[pos][i]=t.a[j][i]; if(pos!=j) t.a[j][i]=0; pos--; } } } void change2(Node &t) { int pos=1; for(int i=1;i<=m;i++) { int f=0; for(int j=1;j<=n;j++) if(t.a[j][i]!=0) { f=1; break; } if(f) { for(int j=1;j<=n;j++) { t.a[j][pos]=t.a[j][i]; if(pos!=i) t.a[j][i]=0; } pos++; } } } void solve(Node &s,int sum) { if(sum+get(s)<=ans) return ; Node t=s; Node p=s; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(t.a[i][j]==0||p.a[i][j]==0) continue; int tmp=dfs(t,i,j,t.a[i][j],p); if(tmp>=3) { change1(t); change2(t); //Sleep(12000); ans=max(ans,sum+tmp*tmp); solve(t,sum+tmp*tmp); } t=s; } } } int main() { while(scanf("%d%d%d",&n,&m,&k)!=EOF) { Node s; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&s.a[i][j]); ans=0; solve(s,0); printf("%d\n",ans); } return 0; } /** 3 3 5 0 0 3 0 2 0 0 0 2 */
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:UVW源码漫谈(三)
- HDU-2955-Robberies(0-1背包) 2020-03-30
- hdu1455 拼木棍(经典dfs) 2020-02-29
- anniversary party_hdu1520 2020-02-16
- hdu1062 text reverse 2020-01-27
- hdu4841 2020-01-26
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash