TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2165
  • 题目
  • P2165【搜索】四色问题
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

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

    输入格式

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

    输出格式

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

    样例输入

    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

    样例输出

    1213134
    384

    提示

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