#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
const int a = 36
/*319 239*/
void inig(void)
void drw(int X, int Y)
void fill(int X, int Y,int t[7])
int main(void)
{
int count = 0, i, j, k, v
FILE *data
int t[7]
inig()
data = fopen("data.txt", "w")
for(t[0] = 1t[0]<5t[0]++)
{
for(t[1] = 1t[1]<5t[1]++)
{
if(t[1]==t[0])
continue
for(t[2] = 1t[2]<5t[2]++)
{
if(t[2]==t[0])
continue
for(t[3] = 1t[3]<5t[3]++)
{
if(t[3]==t[1] || t[3]==t[2])
continue
for(t[4] = 1t[4]<5t[4]++)
{
if(t[4]==t[0] || t[4]== t[2])
continue
for(t[5] = 1t[5]<5t[5]++)
{
if(t[5]==t[1] || t[5]== t[3])
continue
for(t[6] = 1t[6]<5t[6]++)
{
if(t[6]==t[2] || t[6]== t[3])
continue
for(i=0i<7i++)
{
fprintf(data," %d", t[i])
}
count++
fprintf(data,"\n")
}
}
}
}
}
}
}
fclose(data)
printf(" count = %d\n", count)
fopen("data.txt","r")
for(v=0v<countv = v+7)
{
cleardevice()
printf("%d", v )
for(i=50i<580i += 630/6)
{
for(j=50j<500j += 540/6)
{
for(k=0k<7k++)
fscanf(data,"%d", &(t[k]))
drw(i,j)
fill(i,j,t)
}
}
getch()
}
getch()
closegraph()
return 0
}
void drw(int X, int Y)
{
rectangle(X-a, Y-a, X+a, Y+a)
line(X-a, Y+a, X+a, Y-a)
line(X-a, Y-a, X+ a/2, Y+ a/2)
line(X, Y+a, X+a, Y)
line(X- a/2, Y+ a/2, X, Y+a)
line(X+ a/2, Y- a/2, X+a, Y)
}
void fill(int X, int Y,int t[7])
{
int i
for(i=-a+2i<0i++)
{
setcolor(t[0])
line(X+i-1, Y+i, X+i-1, Y)
line(X+i-1, Y-i, X+i-1, Y)
}
for(i=0i<a-1i++)
{
setcolor(t[1])
line(X+i, Y-i-1, X+i, Y-a+1)
line(X-i, Y-i-1, X-i, Y-a+1)
setcolor(t[6])
line(X+1+i, Y-1+a, X+1+i, Y-i+a)
}
for(i=a/2+1i<a-1i++)
{
setcolor(t[5])
line(X+i+1, Y-i, X+i+1, Y+i-a)
setcolor(t[4])
line(X-i, Y+i+1, X+i-a, Y+i+1)
setcolor(t[2])
line(X+i-a+1, Y-i+a, X+i-a+1, Y+i)
line(X-i+a-2, Y-i+a, X-i+a-2, Y+i)
setcolor(t[3])
line(X+i-a/2+1, Y-i+a/2, X+i-a/2+1, Y+i-a/2)
line(X-i+a*3/2-2, Y-i+a/2, X-i+a*3/2-2, Y+i-a/2)
}
}
void inig(void)
{
int gdriver = DETECT, gmode, errorcode
/* initialize graphics, local variables */
initgraph(&gdriver, &gmode, "")
errorcode = graphresult()
if (errorcode != grOk)
{
printf("Graphics error: %s\n",
grapherrormsg(errorcode))
printf("Press any key to halt:")
getch()
exit(1)
}
setcolor(getmaxcolor())
}
不同的C有不同的绘图函数。头文件名和库名也不同。VC++中用MFC, CDC类中有绘图函数,三维用opengl绘图函数。纯C可用GLUT画二维三维图。
例如:
画直线,画弧:
pDC->MoveTo(50,50)pDC->LineTo(50,200)
pDC->Arc(50,50,150,150,100,50,100,50)
画涂色的椭圆
pDC->SelectObject(aBrush)
pDC->Ellipse(350,50,450,150)
画3维多边形:
glBegin(GL_POLYGON)
glNormal3f(cube_n[5][0],cube_n[5][1],cube_n[5][2])
glVertex3f(cube_v[5][0],cube_v[5][1],cube_v[5][2])
glNormal3f(cube_n[1][0],cube_n[1][1],cube_n[1][2])
。。。。
glEnd()
从一个省开始,给它涂上任意一种颜色1,遍历它旁边的省份,涂上与已经涂色并于他相邻的省份不同的颜色就行了。理论上4种颜色就够了.地图的四色问题嘛!
可能会有多组解。用递归(dfs)就可以输出所有解了。
地图着色算法C语言源代码
前面我写了一个地图着色(即四色原理)的C源代码。
写完以后想了一下,感觉还不完善,因为从实际操作的角度来考虑,四种可用的颜色放在旁边,不同的人可能会有不同的选择顺序,另外,不同的人可能会选择不同的城市作为着色的起点,而当时的程序没有考虑这个问题。于是,把程序修改为下面的样子,还请同行分析并指出代码中的不足之处:
#i nclude <stdio.h>
#define N 21
int allcolor[4]/*可用的颜色*/
int ok(int metro[N][N],int r_color[N],int current)
{/*ok函数和下面的go函数和原来的一样,保留用来比较两种算法*/
int j
for(j=1j<currentj++)
if(metro[current][j]==1&&r_color[j]==r_color[current])
return 0
return 1
}
void go(int metro[N][N],int r_color[N],int sum,int current)
{
int i
if(current<=sum)
for(i=1i<=4i++)
{
r_color[current]=i
if(ok(metro,r_color,current))
{
go(metro,r_color,sum,current+1)
return
}
}
}
void color(int metro[N][N],int r_color[N],int sum,int start)
{
int i,j,k
r_color[start]=allcolor[0]
for(i=start+1i!=starti=(i+1)%(sum+1))/*把所有编号看作一个环*/
if(i==0)/*城市号从1开始编号,故跳过0编号*/
continue
else
for(j=0j<4j++)
{
r_color[i]=allcolor[j]/*选取下一种颜色,根据allcolor中颜色顺序不同,结果不同*/
for(k=1k<ik++)/*检查是否有冲突,感觉还可以改进,如使用禁忌搜索法*/
if(metro[i][k]==1&&r_color[k]==r_color[i])
break
if(k>=i)
break
}
}
void main()
{
int r_color[N]={0}
int t_color[N]={0}
int i
int start/*着色的起点*/
int metro[N][N]={{0},
{0,1,1,1,1,1,1},
{0,1,1,1,1},
{0,1,1,1,0,0,1},
{0,1,1,0,1,1},
{0,1,0,0,1,1,1,0,0,1,0,0,0,0,0,0,1},
{0,1,0,1,0,1,1,1,1,1},
{0,0,0,0,0,0,1,1,1},
{0,0,0,0,0,0,1,1,1,1,0,0,1},
{0,0,0,0,0,1,1,0,1,1,0,0,1,1,1,0,1},
{0,0,0,0,0,0,0,0,0,0,1,1,0,1,0,1,0,0,0,1},
{0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1},
{0,0,0,0,0,0,0,0,1,1,0,1,1,1,0,0,0,0,0,1,1},
{0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,1,1,1,0,1},
{0,0,0,0,1,0,0,0,1,0,0,0,0,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1},
{0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,1,0,0,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1}}
allcolor[0]=1allcolor[1]=2allcolor[2]=3allcolor[3]=4/*选色顺序,顺序不同,结果不同*/
start=1
/* clrscr()*/
printf("\nAll color is:\n")
for(i=0i<4i++)/*当前选色顺序*/
printf("%d",allcolor[i])
go(metro,r_color,20,1)
printf("\nFirst method:\n")
for(i=1i<=20i++)
printf("%3d",r_color[i])
color(metro,t_color,20,start)
printf("\nSecond method:\n")
printf("\nAnd the start metro is:%d\n",start)
for(i=1i<=20i++)
printf("%3d",t_color[i])
}
说是人性化着色,其实还有一个问题没有考虑,那就是操作员跳跃式着色,就像大家玩“扫雷”游戏一样。其实也容易实现,可以像定义选色顺序一样定义着色顺序。