首页 > 代码库 > xtu summer individual 1 A - An interesting mobile game

xtu summer individual 1 A - An interesting mobile game

2024-07-15 09:04:01   223人阅读

An interesting mobile game

Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 3295
64-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.
 

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 }
View Code

 


联系
我们