[CODEVS1116]四色问题

题目描述 Description

给定N（小于等于8）个点的地图，以及地图上各点的相邻关系，请输出用4种颜色将地图涂色的所有方案数（要求相邻两点不能涂成相同的颜色）

数据中0代表不相邻，1代表相邻

输入描述 Input Description

第一行一个整数n，代表地图上有n个点

接下来n行，每行n个整数，每个整数是0或者1。第i行第j列的值代表了第i个点和第j个点之间是相邻的还是不相邻，相邻就是1，不相邻就是0.

我们保证a[i][j] = a[j][i] （a[i,j] = a[j,i]）

输出描述 Output Description

染色的方案数

样例输入 Sample Input

8
0 0 0 1 0 0 1 0 
0 0 0 0 0 1 0 1 
0 0 0 0 0 0 1 0 
1 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 1 0 0 0 0 0 0 
1 0 1 0 0 0 0 0 
0 1 0 0 0 0 0 0

样例输出 Sample Output

15552

数据范围及提示 Data Size & Hint

n<=8

var a:array[1..10,1..10]of longint;
    color:array[1..10]of longint;
    n,m,i1,j1:longint;
    sum:longint=0;
{function p(w:longint):boolean;
var i:longint=1;
begin
  p:=true;
  while((i<w)and(color[w]*a[i,w]<>color[i])) do i:=i+1;
  if w>=n then exit(false);
end;}
procedure sise(x:longint);
var i,j:longint;
    b:boolean;
begin
  if x>n then
   begin
    inc(sum);
exit;
{必须要退出否则无法进入下一个循环}
   end;
  for i:=1 to 4 do
   begin
    b:=true;
    for j:=1 to 4 do
    if (a[j,x]=1)and(color[j]=i) then b:=false;
    if ((x<=n)and b) then
     begin
      color[x]:=i;
      sise(x+1);
     end;
    color[x]:=0;
   end;
end;
begin
  fillchar(color,sizeof(color),0);
  read(n);
  for i1:=1 to n do
   for j1:=1 to n do
    read(a[i1,j1]);
  sise(1);
  writeln(sum);
end.