曹文信息在线OJ
Home
ProblemSet
Source/Category
Contest
Status
Ranklist
F.A.Qs
Login
Register
5780: Colour2
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：3
Solved：24
Submit
Submit Record
Statistics
Web Board
ShowOff!
Description
名的四色定理你一定听说过吧？这可是近代世界三大数学难题之一唷（顺便提上一句，另外两个是费马定理和哥德巴赫猜想）。 四色定理的提出来自英国。1852年，毕业于伦敦大学的弗南西斯?格思里(Francis Guthrie)在一家科研单位搞地图着色工作时，发现了一种有趣的现象：“看来，每幅地图都可以用四种颜色着色，使得有共同边界的国家着上不同的颜色。”（注意：只要求有公共边的区域不同色就可以，只有公共顶点的同色也没关系）这个结论能不能从数学上加以严格证明呢？他和在大学读书的弟弟格里斯决心试一试。兄弟二人为证明这一问题而使用的稿纸已经堆了一大叠，可是研究工作没有进展。 1852年10月23日，他的弟弟就这个问题的证明请教他的老师、著名数学家德?摩尔根，摩尔根也没有能找到解决这个问题的途径，于是写信向自己的好友、著名数学家哈密尔顿爵士请教。哈密尔顿接到摩尔根的信后，对四色问题进行论证。但直到1865年哈密尔顿逝世为止，问题也没有能够解决。 直到1976年，在J. Koch的算法的支持下，美国数学家阿佩尔(Kenneth Appel)与哈肯(Wolfgang Haken)在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，作了100亿判断，才终于完成了四色定理的证明。 你的任务相对那些数学家们来说当然要容易得多：你只要编写一个程序，计算一下在给定的一张有N个区域的地图上，用四种颜色填充不同区域，并保证有公共边的区域不同色的方案数有多少就可以了。
Input
若干行，第一行一个n，表示那个区域；
接下来的n行，每行n个数，表示是否相邻的邻接矩阵。
Output
一行，包含一个整数，表示方案数。
Sample Input
Copy
6 0 1 0 1 0 1 1 0 1 0 0 0 0 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 0 1 1 0 1 1 1 0
Sample Output
Copy
336