首页 > 代码库 > xtu summer individual 1 A - An interesting mobile game
xtu summer individual 1 A - An interesting mobile game
An interesting mobile game
Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 329564-bit integer IO format: %I64d Java class name: Main
XQ,one of the three Sailormoon girls,is usually playing mobile games on the class.Her favorite mobile game is called “The Princess In The Wall”.Now she give you a problem about this game.
Can you solve it?The following picture show this problem better.
This game is played on a rectangular area.This area is divided into some equal square grid..There are N rows and M columns.For each grid,there may be a colored square block or nothing.
Each grid has a number.
“0” represents this grid have nothing.
“1” represents this grid have a red square block.
“2” represents this grid have a blue square block.
“3” represents this grid have a green square block.
“4” represents this grid have a yellow square block.
1. Each step,when you choose a grid have a colored square block, A group of this block and some connected blocks that are the same color would be removed from the board. no matter how many square blocks are in this group.
2. When a group of blocks is removed, the blocks above those removed ones fall down into the empty space. When an entire column of blocks is removed, all the columns to the right of that column shift to the left to fill the empty columns.
Now give you the number of the row and column and the data of each grid.You should calculate how many steps can make the entire rectangular area have no colored square blocks at least.
Can you solve it?The following picture show this problem better.
This game is played on a rectangular area.This area is divided into some equal square grid..There are N rows and M columns.For each grid,there may be a colored square block or nothing.
Each grid has a number.
“0” represents this grid have nothing.
“1” represents this grid have a red square block.
“2” represents this grid have a blue square block.
“3” represents this grid have a green square block.
“4” represents this grid have a yellow square block.
1. Each step,when you choose a grid have a colored square block, A group of this block and some connected blocks that are the same color would be removed from the board. no matter how many square blocks are in this group.
2. When a group of blocks is removed, the blocks above those removed ones fall down into the empty space. When an entire column of blocks is removed, all the columns to the right of that column shift to the left to fill the empty columns.
Now give you the number of the row and column and the data of each grid.You should calculate how many steps can make the entire rectangular area have no colored square blocks at least.
Input
There are multiple test cases. Each case starts with two positive integer N, M,(N, M <= 6)the size of rectangular area. Then n lines follow, each contains m positive integers X.(0<= X <= 4)It means this grid have a colored square block or nothing.
Output
Please output the minimum steps.
Sample Input
5 60 0 0 3 4 40 1 1 3 3 32 2 1 2 3 31 1 1 1 3 32 2 1 4 4 4
Sample Output
4
Source
2010 “HDU-Sailormoon” Programming Contest
解题:IDA*,每次优先选择能使消除数目多的颜色进行搜索。写的第一道IDA*题目。。。。。IDA*不要存储状态,真是极好的
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <vector> 6 #include <climits> 7 #include <algorithm> 8 #include <cmath> 9 #include <queue> 10 #define LL long long 11 #define INF 0x3f3f3f 12 using namespace std; 13 int table[8][8],r,c,ans,cnt; 14 const int dir[4][2] = {0,-1,0,1,-1,0,1,0}; 15 bool vis[8][8]; 16 struct node{ 17 int x,y; 18 }; 19 struct po{ 20 int x,y,c; 21 }; 22 bool check(int (*t)[8]) { 23 for(int i = r; i ; i--) { 24 for(int j = 1; j <= c; j++) 25 if(t[i][j]) return false; 26 } 27 return true; 28 } 29 bool cmp(const po &a,const po &b){ 30 return a.c > b.c; 31 } 32 void calc(int (*t)[8],int x,int y,const int color){ 33 vis[x][y] = true; 34 cnt++; 35 for(int i = 0; i < 4; i++){ 36 int px = x+dir[i][0]; 37 int py =y+dir[i][1]; 38 if(!vis[px][py] && t[px][py] == color) 39 calc(t,px,py,color); 40 } 41 } 42 void cancle(int (*t)[8],int x,int y,const int color){ 43 bool vis[8][8] = {false}; 44 queue<node>q; 45 vis[x][y] = true; 46 int i,j,px,py; 47 t[x][y] = 0; 48 q.push((node){x,y}); 49 while(!q.empty()){ 50 node temp = q.front(); 51 q.pop(); 52 for(i = 0; i < 4; i++){ 53 px = temp.x+dir[i][0]; 54 py = temp.y+dir[i][1];//这个地方写成dir[i][0]害我调了很久 55 if(!vis[px][py] && t[px][py] == color){ 56 vis[px][py] = true; 57 t[px][py] = 0; 58 q.push((node){px,py}); 59 } 60 } 61 } 62 } 63 void shift(int (*t)[8]){ 64 int i,j,k; 65 bool isempty[8] = {false}; 66 for(j = 1; j <= c; j++){ 67 for(i = r-1; i; i--){ 68 for(k = i;k < r &&!t[k+1][j]&&t[k][j]; k++) 69 swap(t[k+1][j],t[k][j]); 70 } 71 if(!t[r][j]) isempty[j] = true; 72 } 73 for(j = c-1; j; j--){ 74 if(isempty[j]){ 75 for(i = 1; i <= r; i++){ 76 for(k = j; k <= c; k++) 77 t[i][k] = t[i][k+1]; 78 } 79 } 80 } 81 } 82 bool dfs(int (*t)[8],int step){ 83 int mp[8][8],i,j,m = 0; 84 bool flag; 85 if(check(t) && ans == step) return true; 86 if(step > ans) return false; 87 po p[40]; 88 memset(vis,false,sizeof(vis)); 89 for(i = r; i; i--){ 90 flag = true; 91 for(j = 1; j <= c; j++){ 92 if(t[i][j]) flag = false; 93 if(t[i][j] && !vis[i][j]){ 94 cnt = 0; 95 calc(t,i,j,t[i][j]); 96 p[m++] = (po){i,j,cnt}; 97 } 98 } 99 if(flag) break;100 }101 sort(p,p+m,cmp);102 for(i = 0; i < m; i++){103 memcpy(mp,t,sizeof(mp));104 cancle(mp,p[i].x,p[i].y,t[p[i].x][p[i].y]);105 shift(mp);106 if(dfs(mp,step+1)) return true;107 }108 return false;109 }110 int main() {111 int i,j;112 while(~scanf("%d %d",&r,&c)) {113 memset(table,0,sizeof(table));114 for(i = 1; i <= r; i++)115 for(j = 1; j <= c; j++)116 scanf("%d",table[i]+j);117 if(check(table)) {puts("0");continue;}118 for(ans = 1;; ans++)119 if(dfs(table,0)) break;120 printf("%d\n",ans);121 }122 return 0;123 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。