「CODEVS2495」水叮当的舞步
题目描述 Description
水叮当得到了一块五颜六色的格子形地毯作为生日礼物，更加特别的是，地毯上格子的颜色还能随着踩踏而改变。
为了讨好她的偶像虹猫，水叮当决定在地毯上跳一支轻盈的舞来卖萌~~~地毯上的格子有N行N列，每个格子用一个0~5之间的数字代表它的颜色。
水叮当可以随意选择一个0~5之间的颜色，然后轻轻地跳动一步，左上角的格子所在的联通块里的所有格子就会变成她选择的那种颜色。这里连通定义为：两个格子有公共边，并且颜色相同。
由于水叮当是施展轻功来跳舞的，为了不消耗过多的真气，她想知道最少要多少步才能把所有格子的颜色变成一样的。
输入描述 Input Description
每个测试点包含多组数据。
每组数据的第一行是一个整数N，表示地摊上的格子有N行N列。
接下来一个N*N的矩阵，矩阵中的每个数都在0~5之间，描述了每个格子的颜色。
N=0代表输入的结束。
输出描述 Output Description
对于每组数据，输出一个整数，表示最少步数。
样例输入 Sample Input
2
0 0
0 0
3
0 1 2
1 1 2
2 2 1
0
样例输出 Sample Output
0
3
数据范围及提示 Data Size & Hint
对于30%的数据，N<=5
对于50%的数据，N<=6
对于70%的数据，N<=7
对于100%的数据，N<=8，每个测试点不多于20组数据。第二组样例解释：
0 1 2 1 1 2 2 2 2 1 1 1
1 1 2 –> 1 1 2 –> 2 2 2 –> 1 1 1
2 2 1 2 2 1 2 2 1 1 1 1
来源：Nescafe 21
代码
迭代深搜20分
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
#include<iostream> #include<cstdio> using namespace std; int s,n,mp[9][9]; int xx[4]={1,-1,0,0},yy[4]={0,0,-1,1}; bool ans; bool judans() { int t=mp[1][1]; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(mp[i][j]!=t)return 0; return 1; } void doit(int a,int b,int x,int y) { mp[a][b]=y; for(int i=0;i<4;i++) { int nowx=a+xx[i],nowy=b+yy[i]; if(nowx<1||nowy<1||nowx>n||nowy>n)continue; if(mp[nowx][nowy]==x)doit(nowx,nowy,x,y); } } void search(int k) { if(k==s){if(judans())ans=1;return;} if(ans)return; for(int c=0;c<=5;c++) { int t[9][9]; if(mp[1][1]==c)continue; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) t[i][j]=mp[i][j]; doit(1,1,mp[1][1],c); search(k+1); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) mp[i][j]=t[i][j]; } } int main() { while(1) { scanf("%d",&n);ans=0; if(n==0)break; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&mp[i][j]); for(s=0;;s++) { search(0); if(ans){printf("%d\n",s);break;} } } return 0; } |
加个A*，看看题解。。
我们可以发现，每次寻找左上角的格子所在的联通块耗费的时间常数巨大。因此我们在这里寻求突破。
我们引入一个N*N的v数组。左上角的格子所在的联通块里的格子标记为1。左上角联通块周围一圈格子标记为2，其它格子标记为0。如果某次选择了颜色c，我们只需要找出标记为2并且颜色为c的格子，向四周扩展，并相应地修改v标记，就可以不断扩大标记为1的区域，最终如果所有格子标记都是1，那么显然找到了答案。
期望得分：90~100分。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
#include<iostream> #include<cstring> #include<cstdio> using namespace std; int s,n,mp[9][9],mark[9][9]; int xx[4]={1,-1,0,0},yy[4]={0,0,-1,1},used[6]; bool ans; int get() { int t=0; memset(used,0,sizeof(used)); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(!used[mp[i][j]]&&mark[i][j]!=1) { used[mp[i][j]]=1; t++; } return t; } void dfs(int a,int b,int x) { mark[a][b]=1; for(int i=0;i<4;i++) { int nowx=a+xx[i],nowy=b+yy[i]; if(nowx<1||nowy<1||nowx>n||nowy>n||mark[nowx][nowy]==1)continue; mark[nowx][nowy]=2; if(mp[nowx][nowy]==x)dfs(nowx,nowy,x); } } int fill(int x) { int t=0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(mark[i][j]==2&&mp[i][j]==x) { t++; dfs(i,j,x); } return t; } void search(int k) { int v=get(); if(!v)ans=1; if(k+v>s||ans)return; int temp[10][10]; for(int i=0;i<=5;i++) { memcpy(temp,mark,sizeof(mark)); if(fill(i))search(k+1); memcpy(mark,temp,sizeof(mark)); } } int main() { while(1) { memset(mark,0,sizeof(mark)); scanf("%d",&n);ans=0; if(n==0)break; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&mp[i][j]); dfs(1,1,mp[1][1]); for(s=0;;s++) { search(0); if(ans){printf("%d\n",s);break;} } } return 0; } |
OI 课件=>
