TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P2165
  • Problem
  • P2165【搜索】四色问题
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Description

    四色猜想:“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。”——弗南西斯·格思里
    有形如下列图形的地图,图中每一块区域代表一个国家,现请你用红(1)、兰(2)、黄(3)、绿(4)四种颜色给这些国家填上颜色,要求每一国家用一种颜色,且任意两个相邻国家的颜色不能相同,请给出一种符合条件的填色方案。给出国家的数量(<=20)和它们的邻接关系。找出可行的方案总数,按第1个国家到第n个国家输出方案,只输出其中字典序最小的一种。

    Input Format

    第一行,一个整数n,表示总的国家数(n<=20)
    接下来一个n*n的矩阵,用空格间隔的0和1表示国家间的相邻关系,如果第i行第j列是1,表明第i个国家与第j个国家相邻

    Output Format

    第一行,一种字典序最小的方案
    第二行,一个整数,表示总的方案数

    Sample Input

    7
    0 1 0 0 0 0 1
    1 0 1 1 1 1 1
    0 1 0 1 0 0 0
    0 1 1 0 1 0 0
    0 1 0 1 0 1 0
    0 1 0 0 1 0 1
    1 1 0 0 0 1 0

    Sample Output

    1213134
    384

    Hint

    下列是可行方案的一部分
    1213134
    1324212
    2123434
    2341241
    3124242
    3243131
    4132342
    4243413
    .....
    其中字典序最小的是1213134