DFS 着色最少颜色

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
#include <stdio.h>
#include <iostream>
using namespace std;
int t;
int count=0;
int arr[20][20];
int color[20]={0};
bool judge(int x){
for(int j=1;j<=t;j++){
if(arr[x][j]==1 && color[x]==color[j]){
return false;
}
}
return true;
}
int DFS(int index,int num){
if(index==t+1){
return 1;
}
for(int i=1;i<=num;i++){
color[index]=i;
if(judge(index)){
if(DFS(index+1,num))
return 1;
}
}
return 0;
}
void init(){
count=1;
for(int i=1;i<t;i++){
color[i]=0;
}
}
int main(){
//freopen("1.txt","r",stdin); //打开文件，测试程序，可以取消这行注释
while(cin>>t && t!=0){
init();
for(int i=1;i<=t;i++)
for(int j=1;j<=t;j++)
cin>>arr[i][j];
for(int i=1;i<=t;i++)
if(DFS(1,i)){
count=i;
break;
}
cout<<count<<endl;
}
//fclose(stdin);//关闭文件
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
0 0
0 0
4
0 1 1 0
1 0 1 1
1 1 0 1
0 1 1 0
4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
5
0 1 1 1 0
1 0 1 1 1
1 1 0 1 0
1 1 1 0 1
0 1 0 1 0
0