#include <stdio.h> #define N 10 void output(int color[]){ /*输出一种着色方案*/ int i ; for ( i = 0 ; i < N ; i++ ) printf( "%4d",color[i] ) ; printf("\n") ; } int back(int *ip,int color[ ]){ /*回溯*/ int c = 4 ; while ( c == 4 ){ if ( *ip <= 0 ) return 0 ; --(*ip) ; c = __(1)__ ; color[*ip] = -1 ; } return c ; } /*检查区域 i ,对 c 种颜色的可用性*/ int colorOK(int I,int c,int[][N],int color[ ]){ int j ; for ( j = 0 ; j < i ; j++ ) if ( __(2)__ ) return 0 ; return 1 ; } /*为区域i选一种可着的颜色*/ int select(int I,int c,int adj[][N],int color[ ]){ int k ; for(k = c ; k <= 4 ; k++ ) if( colorOK( __(3)__ )) return k ; return 0 ; } int coloring(int adj[][N]){ /*寻找各种着色方案*/ int color[N],I,c,cnt ; for(i = 0 ; i < N ; i++) color[i] = -1 ; i = c = 0 ; cnt = 0 ; while(1){ if((c = __(4)__ ) == 0){ c = back( &I,color); if ( c == 0) return cnt; } else { __(5)__ ; i++ ; if(i == N){ output(color) ; ++cnt ; c = back( &I,color ) ; } e1se c = 0 ; } } } void main(){ int adj[N][N] = { {0,1,0,1,1,1,1,1,1,1}, {1,0,1,1,0,1,1,1,1,0}, {0,1,0,1,0,1,1,0,1,1}, {1,1,1,0,1,1,0,0,1,1}, {1,0,0,1,0,1,0,0,0,0}, {1,1,1,1,1,0,1,0,0,1}, {1,1,1,0,0,1,0,0,1,0}, {1,1,0,0,0,0,0,0,1,1}, {1,1,1,1,0,0,1,1,0,1}, {1,0,1,1,0,1,0,1,1,0} } ; printf("共有%d组解.\n",coloring(adj)); } |