TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P1407
  • 题目
  • P1407【分类练习4.分治法】地毯填补问题
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    相传在一个古老的阿拉伯国家里,有一座宫殿。宫殿里有个四四方方的格子迷宫,国王选择驸马的方法非常特殊,也非常简单:公主就站在其中一个方格子上,只要谁能用地毯将除公主站立的地方外的所有地方盖上,美丽漂亮聪慧的公主就是他的人了。公主这一个方格不能用地毯盖住,毯子的形状有所规定,只能有四种选择(如图4-l)

    并且每一方格只能用一层地毯,迷宫的大小为$(2^k)^2$的方形。当然,也不能让公主无限制的在那儿等,对吧?由于你使用的是计算机,所以实现时间为1s。

    输入格式

    第一行:$k$,即给定被填补迷宫的大小为$2^k(1\le k\le10)$。
    第二行:$x\ y$,即给出公主所在方格的坐标($x$为行坐标,$y$为列坐标),$x$和$y$之间有一个空格隔开。

    输出格式

    将迷宫填补完整的方案:每一补(行)为$x\ y\ c$($x,y$为毯子拐角的行坐标和列坐标,$c$为使用毯子的形状,具体见上面的图 具体见下图,毯子形状分别用$1,2,3,4$表示,$x,y,c$之间用一个空格隔开)。

    样例输入

    3
    3 3

    样例输出

    5 5 1
    2 2 4
    1 1 4
    1 4 3
    4 1 2
    4 4 1
    2 7 3
    1 5 4
    1 8 3
    3 6 3
    4 8 1
    7 2 2
    5 1 4
    6 3 2
    8 1 2
    8 4 1
    7 7 1
    6 6 1
    5 8 3
    8 5 2
    8 8 1


    来源  感谢nodgd重新解读样例