阅读下列程序说明和C代码,将应填入(n)处。【程序5说明】 著名的四色定理指出任何平面区域图均可用四

阅读下列程序说明和C代码，将应填入(n)处。

【程序5说明】

著名的四色定理指出任何平面区域图均可用四种颜色着色，使相邻区域着不同的颜色。本程序对给定的区域图找出所有可能的不超过四种颜色的着色方案。

程序中用1～4表示四种颜色。要着色的N个区域用0～N-1编号，区域相邻关系用 adj[][]矩阵表示，矩阵的i行j列的元素为1，表示区域i与区域j相邻；矩阵的i行j列的元素为0，表示区域i与区域j不相邻。数组color[]用来存储着色结果，color[i]的值为区域i所着颜色。

【程序5】

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)；

}else 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))；

}

正确答案：

(1)color[*ip](2)adj[i][j]!=0 && color[j]==c(3)ikadjcolor(4)select(ic+1adjcolor)(5)color[i]=c(1)color[*ip](2)adj[i][j]!=0 && color[j]==c(3)i，k，adj，color(4)select(i，c+1，adj，color)(5)color[i]=c 解析：(1)Back()函数将color数组中紧邻*ip位置的，颜色值为 4的一个连续区域的元素