填色问题(PASCAL)

来源:百度知道 编辑:UC知道 时间:2024/06/05 11:20:01
一张地图,有12个区域,用4种颜色着色.要求相邻的区域不用同种颜色,问共有多少种方案(PASCAL)

这不就是著名的四色问题吗?
答案如下:
{问题描述:任何一张地图只要用四种颜色进行填涂,就可以保证相邻省份不同色}

program tt;
const num=20;
var a:array [1..num,1..num] of 0..1;
s:array [1..num] of 0..4; {用1-4分别代表RBWY四种颜色;0代表末填进任何颜色}
k1,k2,n:integer;
function pd(i,j:integer):boolean;{判断可行性:第I个省填上第J种颜色}
var k:integer;
begin
for k:=1 to i-1 do {一直从第一个省开始进行比较一直到I省减一的那个省,目的是对已经着色的省份来进行比较,因为>I的省还没 有着色,比较没有意义,着色的顺序是先第一、二、三……I个省}
if (a[i,k]=1) and (j=s[k]) then {省I和省J相邻且将填进的颜色和已有的颜色相同}
begin
pd:=false; {即不能进行着色}
exit; {退出当前函数}
end;
pd:=true; {可以进行着色}
end;

procedure print;{打印结果}
var k:integer;
begin
for k:=1 to n do{将数字转为RBWY串}
case s[k] of
1:write('R':4);
2:write('B':4);
3:write('W':4);
4:write('Y&