題目描述:
玩flood-it游戲, 一個(gè)8*8的帶6種顏色的格子. 每次占領(lǐng)與已占領(lǐng)的聯(lián)通塊相鄰的聯(lián)通塊, 問最少幾次可以全部占領(lǐng)完. 第一次占領(lǐng)左上角.
算法分析:
不知道是不是數(shù)據(jù)變?nèi)趿?還是服務(wù)器太快了. 最基本的IDA*就可以過. 估價(jià)函數(shù)設(shè)成最傻的都可以.
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 using namespace std;
5 const int N = 8;
6 typedef pair<int,int> pnt;
7 int vis[N][N], num[N][N], n, tp;
8 pnt Q[N*N];
9 inline bool fit(int x,int y){
10 return x >= 0 && x < n && y >= 0 && y < n && !vis[x][y];
11 }
12 inline void bfs(int sx,int sy) {
13 int head = 0, tail = 1;
14 vis[sx][sy] = 1;
15 Q[0] = make_pair(sx, sy);
16 int c = num[sx][sy];
17 //cout<< "bfs: "<<endl;
18 //cout<< c << endl;
19 while(head < tail) {
20 pnt u = Q[head ++];
21 for(int i = 0; i < 4; i++){
22 int x = u.first + (i == 0) - (i == 1);
23 int y = u.second + (i == 2) - (i == 3);
24 if(fit(x,y) && num[x][y] == c){
25 // cout<<"v: "<<x<<" "<<y<<" "<< num[x][y]<<endl;
26 vis[x][y] = 1;
27 Q[tail ++] = make_pair(x, y);
28 }}}
29 }
30 typedef unsigned long long ll;
31 inline ll hash(){
32 ll ans = 0;
33 for(int i = 0; i< n; i++)
34 for(int j = 0; j < n; j ++)
35 ans <<= 1, ans ^= vis[i][j];
36 return ans;
37 }
38 inline void rehash(ll t) {
39 for(int i = n-1; i>= 0; i--)
40 for(int j = n-1; j>=0 ;j--, t>>=1)
41 vis[i][j] = t&1;
42 }
43 inline int cal(){
44 int h[6] = {0};
45 for(int i = 0; i < n; i++)
46 for(int j = 0; j< n; j++) if(!vis[i][j])
47 h[num[i][j]] = 1;
48 int ans = 0;
49 for(int i = 0; i < 6; i++)
50 ans += h[i];
51 return ans;
52 }
53 int dfs(int lvl) {
54 //cout<<"lvl: "<<lvl<<endl;
55 if(lvl == tp) return cal() == 0;
56 if(cal()+ lvl > tp) return 0;
57 ll tmp = hash();
58 for(int c = 0; c < 6; c ++){
59 int flag = 0;
60 for(int i = 0; i < n; i++)
61 for(int j = 0; j< n; j++) if(vis[i][j]) {
62 for(int p = 0; p < 4; p ++ ){
63 int x = i + (p == 0) - (p == 1);
64 int y = j + (p == 2) - (p == 3);
65 if(fit(x,y) && num[x][y] == c){
66 bfs(x,y);
67 flag = 1;
68 }
69 }}
70 if(!flag) continue;
71 if(dfs(lvl + 1)) return 1;
72 rehash(tmp);
73 }
74 return 0;
75 }
76 int main(){
77 while(scanf("%d",&n), n) {
78 for(int i = 0; i < n ; i ++)
79 for(int j = 0; j < n; j++)
80 scanf("%d",&num[i][j]);
81 memset(vis, 0, sizeof(vis));
82 bfs(0,0);
83 ll tmp = hash();
84 for(tp=cal();;tp++) {
85 // cout<<tp<<endl;
86 if(dfs(0)) break;
87 rehash(tmp);
88 }
89 printf("%d\n",tp);
90 }
91 }
92
posted on 2012-08-15 20:56
西月弦 閱讀(434)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
解題報(bào)告