Hdu 4090 GemAnd Prince (搜索_2010年北京区域赛)
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4090
题目大意:给定一个n*m，矩阵上每个点都有一个数字,数字范围是1到k，某个数字相同的连通块如果块数大于3，那么我们就可以选择消掉这个连通块，分数是块数的平方，问最优策略下消的最高分数是多少？n,m <= 8
解题思路：下午开了场虚拟比赛，做了两题，这题是最后一个半小时敲得，代码敲了40分钟左右，剩下的时间都在调试，咳，太久没写搜索了，写的各种蛋疼，到赛后才发现一个坑爹的Bug，原来我写判重函数的时候只写了如果这个局面没搜索过就往下搜，却没有写如果搜过会怎么样。自己出的各种数据还像模像样得出正确答案,。
这题我写得很奇葩，和网上大部分解题报告的方法不一样，我是用hash去判重去剪枝，做法是将当前局面压缩成一个字符串丢到map里面去判断之前是否搜过。每次消掉一片后，那些数字会压缩到左下角，其他部分都是0，所以我代码里的n和m是表示有n行和m列是有效的，n和m是动态变化的，这样搜索的时候可以减少很多没必要的遍历和操作。其他都没什么，就像模拟题一样去写就好了。
测试数据:
Input:
5 5 5
1 2 3 4 5
1 2 2 2 1
1 2 1 2 1
1 2 2 2 2
1 2 3 3 5
3 3 3
1 1 1
1 1 1
2 3 3
4 4 3
1 1 1 3
2 1 2 3
1 2 1 3
3 3 3 3
4 4 2
1 2 1 2
2 1 2 1
1 2 1 2
2 1 2 1
8 8 6
1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2
3 3 3 3 3 3 3 3
4 4 4 4 4 4 4 4
5 5 5 5 5 5 5 5
6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6
8 8 6
6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6
OutPut:
166
36
94
128
896
4096
C艹代码:
#include <stdlib.h>#include <stdio.h>#include <map>#include <string>#include <string.h>using namespace std;#define MAX 10struct node { int x,y;}qu[MAX*MAX];map<string,int> hash;int mmap[MAX][MAX],ans;int n,m,K,total;int dir[8][2] = {{1,0},{1,1},{1,-1},{-1,0},{-1,-1},{-1,1},{0,1},{0,-1}};void Print(int temp[][MAX],int n,int m) { for (int i = n-1; i >= 0; --i) for (int j = 0; j < m; ++j) printf("%d%c",temp[i][j],j==m-1?'\n':' ');}void change(int mmap[][MAX],int &n,int &m){ int i,j,k[10],tn = 0,tm = 0; for (j = 0; j < m; ++j) { k[j] = 0; for (i = 0; i < n; ++i) if (mmap[i][j]) mmap[k[j]++][j] = mmap[i][j]; } for (j = 0; j < m; ++j) if (k[j]) { for (i = 0; i < k[j]; ++i) mmap[i][tm] = mmap[i][j]; for (i = k[j]; i < n; ++i) mmap[i][tm] = 0; tm++; if (k[j] > tn) tn = k[j]; } n = tn,m = tm;}int Ok(int temp[][MAX],int vis[][MAX],int i,int j,int n,int m) { int cnt = 0,k; int head = 0,tail = 0; node cur,next; cur.x = i,cur.y = j; qu[head++] = cur; vis[cur.x][cur.y] = 1; while (tail < head) { cur = qu[tail++]; cnt++; for (k = 0; k < 8; ++k) { next.x = cur.x + dir[k][0]; next.y = cur.y + dir[k][1]; if (next.x >= 0 && next.x < n && next.y >= 0 && next.y < m && vis[next.x][next.y] == 0 && temp[next.x][next.y] == temp[i][j]) { qu[head++] = next; vis[next.x][next.y] = 1; temp[next.x][next.y] = 0; } } } temp[i][j] = 0; return cnt >= 3 ? cnt : 0;}string GetHash(int temp[][MAX],int n,int m) { string s = ""; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) s += temp[i][j] + '0'; return s;}void mem(int temp[][MAX],int mmap[][MAX],int n,int m) { memset(temp,0,sizeof(temp)); for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) temp[i][j] = mmap[i][j];}int Dfs(int mmap[][MAX],int n,int m) { if (n * m < 3) return 0; int temp[MAX][MAX],i,j; int vis[MAX][MAX],cnt = 0,ans; memset(vis,0,sizeof(vis)); for (i = 0; i < n; ++i) for (j = 0; j < m; ++j) if (!vis[i][j] && mmap[i][j]) { mem(temp,mmap,n,m); ans = Ok(temp,vis,i,j,n,m); if (ans >= 3) { ans = ans * ans; int tn = n,tm = m; change(temp,tn,tm); string s = GetHash(temp,tn,tm); if (hash.find(s) == hash.end()) ans += Dfs(temp,tn,tm); else ans += hash[s]; if (ans > cnt) cnt = ans; } } hash[GetHash(mmap,n,m)] = cnt; return cnt;}int main() { int i,j,k; while (scanf("%d%d%d",&n,&m,&K) != EOF) { memset(mmap,0,sizeof(mmap)); for (i = n-1; i >= 0; --i) for (j = 0; j < m; ++j) scanf("%d",&mmap[i][j]); hash.clear(); printf("%d\n",Dfs(mmap,n,m)); }}本文ZeroClock原创，但可以转载，因为我们是兄弟。