bzoj3041 水叮当的舞步 IDA*

水叮当的舞步

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 230 Solved: 107
[Submit][Status][Discuss]

Description

水叮当得到了一块五颜六色的格子形地毯作为生日礼物，更加特别的是，地毯上格子的颜色还能随着踩踏而改变。
为了讨好她的偶像虹猫，水叮当决定在地毯上跳一支轻盈的舞来卖萌~~~
地毯上的格子有N行N列，每个格子用一个0~5之间的数字代表它的颜色。
水叮当可以随意选择一个0~5之间的颜色，然后轻轻地跳动一步，左上角的格子所在的联通块里的所有格子就会变成她选择的那种颜色。这里连通定义为：两个格子有公共边，并且颜色相同。
由于水叮当是施展轻功来跳舞的，为了不消耗过多的真气，她想知道最少要多少步才能把所有格子的颜色变成一样的。

Input

每个测试点包含多组数据。
每组数据的第一行是一个整数N，表示地摊上的格子有N行N列。
接下来一个N*N的矩阵，矩阵中的每个数都在0~5之间，描述了每个格子的颜色。
N=0代表输入的结束。

Output

对于每组数据，输出一个整数，表示最少步数。

Sample Input

2
0 0
0 0
3
0 1 2
1 1 2
2 2 1
0

Sample Output

0
3

对于100%的数据，N<=8，每个测试点不多于20组数据。

HINT

Source

Poetize5

题解：

　　用1表示同种颜色，然后2表示1周围的一圈，

　　然后每次从1附件周围去扩散，IDA*，限制步数，就可以过了。

 1 #include<bits/stdc++.h>
 2 typedef long long ll;
 3 const int N=10000000;
 4 const int mod=1000000007;
 5 const double eps=0.00000001;
 6 using namespace std;
 7 inline int read()
 8 {
 9     int x=0,f=1;char ch=getchar();
10     while (ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();}
11     while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
12     return x*f;
13 }
14 int step,n,mp[9][9],flag[9][9];
15 int xx[4]={1,-1,0,0},yy[4]={0,0,-1,1},used[6];
16 bool ans;
17 int get()
18 {
19     int ans=0;
20     memset(used,0,sizeof(used));
21     for(int i=1;i<=n;i++)
22         for(int j=1;j<=n;j++)
23             if(!used[mp[i][j]]&&flag[i][j]!=1)
24             {
25                 used[mp[i][j]]=1;
26                 ans++;
27             }
28     return ans;
29 }
30 void dfs(int a,int b,int c)
31 {
32     flag[a][b]=1;
33     for (int i=0;i<4;i++)
34     {
35         int x=a+xx[i],y=b+yy[i];
36         if (x<1||x>n||y<1||y>n||flag[x][y]==1) continue;
37         flag[x][y]=2;
38         if (mp[x][y]==c) dfs(x,y,c);
39     }
40 }
41 bool fill(int c)
42 {
43     int ans=0;
44     for (int i=1;i<=n;i++)
45         for (int j=1;j<=n;j++)
46             if (flag[i][j]==2&&mp[i][j]==c)
47             {
48                 ans++;
49                 dfs(i,j,c);
50             }
51     return ans;
52 }
53 void search(int s)
54 {
55     int v=get();
56     if (!v) ans=1;
57     if (s+v>step||ans) return;
58     int tmp[10][10];
59     for(int i=0;i<=5;i++)
60     {
61         memcpy(tmp,flag,sizeof(flag));
62         if(fill(i))search(s+1);
63         memcpy(flag,tmp,sizeof(flag));
64     }
65 }
66 int main()
67 {
68     while (1)
69     {
70         n=read();if (n==0) break;
71         for (int i=1;i<=n;i++)
72             for (int j=1;j<=n;j++)
73                 mp[i][j]=read(),flag[i][j]=0;
74         dfs(1,1,mp[1][1]);
75         for (ans=step=0;;step++)
76         {
77             search(0);
78             if (ans){printf("%d
",step);break;}
79         }
80     }
81     return 0;
82 }