题解
1.暴力求解法 (DFS)
对于每一时刻的局面,可以抽象成一个图。问题就是分别求每一时刻图中连通分量的个数。如何求图的连通分量的个数呢?可以使用深度优先搜索DFS。假设图中节点数为N*M,那么每一时刻都需要遍历N*M节点来求取连通分量个数。同样,我们有N*M个时刻。最终的算法复杂度为O( (N*M)2 )。
2.并查集
我们先来看一看何为并查集,这里我不再赘述,分享一篇好文章,那么如何利用并查集优化问题求解呢,思路来自于这里。
实现
1 #include <iostream> 2 3 using namespace std; 4 5 const int MAXSIZE = 1000*1000+1; 6 int uset[MAXSIZE]; 7 int answer[MAXSIZE]; 8 pair<short,short> valueToIndex[MAXSIZE]; 9 const int dx[]={-1,0,0,1},dy[]={0,-1,1,0}; 10 11 //void makeSet(int size) { 12 // for(int i = 1;i <= size;i++) uset[i] = -MAXSIZE; 13 //} 14 15 int find(int x) { 16 int p = x, t; 17 while (uset[p] > 0) p = uset[p]; 18 while (x != p ) { 19 t = uset[x]; 20 uset[x] = p; 21 x = t; 22 } 23 return x; 24 } 25 26 void unionSet(int x, int y) { 27 if ((x = find(x)) == (y = find(y))) return; 28 if (uset[x] < uset[y]) { 29 uset[x] += uset[y]; 30 uset[y] = x; 31 } else { 32 uset[y] += uset[x]; 33 uset[x] = y; 34 } 35 } 36 37 void unionSetRoot(int x,int y) 38 { 39 if (uset[x] < uset[y]) { 40 uset[x] += uset[y]; 41 uset[y] = x; 42 } else { 43 uset[y] += uset[x]; 44 uset[x] = y; 45 } 46 } 47 48 int raw,col; 49 int main() 50 { 51 52 scanf("%d%d",&raw,&col); 53 int size = raw * col; 54 //makeSet(size); 55 56 for(short i=1;i<=raw;i++) 57 for(short j=1;j<=col;j++) 58 { 59 int value; 60 scanf("%d",&value); 61 valueToIndex[value] = make_pair(i,j); 62 } 63 64 for(int evaWater=size-1;evaWater>=1;evaWater--) 65 { 66 int lastEvaWater = evaWater+1; 67 int x = valueToIndex[lastEvaWater].first; 68 int y = valueToIndex[lastEvaWater].second; 69 int lastValueIndex = (x-1)*col +y; 70 uset[lastValueIndex] = -1; 71 answer[evaWater] = answer[lastEvaWater]+1; 72 73 for(int dir=0;dir<4;dir++) 74 { 75 int tx=x+dx[dir],ty=y+dy[dir]; 76 77 if(tx >=1&& tx <=raw && ty>=1 && ty<= col ) 78 { 79 int los =(tx-1)*col+ty; 80 81 if( uset[los] !=0 ) 82 { 83 int key = find(los); 84 int last = find(lastValueIndex); 85 if(last != key) 86 { 87 unionSetRoot(last,key); 88 answer[evaWater]--; 89 } 90 91 } 92 93 } 94 } 95 96 97 } 98 99 100 for (int i=1;i<=size;i++) 101 printf("%d\n",answer[i]); 102 103 return 0; 104 }
代码写得很清晰,一共大概100行,主要是定义并查集,和运用并查集检测周边四个点的集合数。
这代码可以通过CCF的1000*1000 1s评测,运行时间大概在700-800ms,使用内存10M。使用内存数在所有实现中最少,但是时间不是最少。排名第一的同学大概在450ms左右。这个我不清楚如何做到在消除者300ms的差距,因为300ms差距不是简简单单优化细节可以做的。就目测他们应该是保存了更多的数据。
抛砖引玉
有没有同学还能更进一步的优化算法或是有更好的想法,争取再砍下去一半时间。期待你的回复~~~~~忘不吝赐教~~~~~