P4460 [CQOI2018]解锁屏幕

    • 315通过
    • 1K提交
  • 题目提供者 Xeonacid
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 广度优先搜索,BFS 状态压缩,状压 各省省选 2018 重庆
  • 难度 省选/NOI-
  • 时空限制 1000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    使用过Android 手机的同学一定对手势解锁屏幕不陌生。Android 的解锁屏幕由3X3 个点组成,手指在屏幕上画一条线,将其中一些点连接起来,即可构成一个解锁图案。如下面三个例子所示:

    题目描述

    画线时还需要遵循一些规则:

    1. 连接的点数不能少于4 个。也就是说只连接两个点或者三个点会提示错误。

    2. 两个点之间的连线不能弯曲。

    3. 每个点只能“使用”一次,不可重复。这里的“使用”是指手指划过一个点,该点变绿。

    4. 两个点之间的连线不能“跨过”另一个点,除非那个点之前已经被“使用”过了。

    对于最后一条规则,参见下图的解释。左边两幅图违反了该规则; 而右边两幅图(分别为2->4-1-3-6 和6->5-4->1->9-2) 则没有违反规则,因为在“跨过”点时,点已经被“使用”过了。

    现在工程师希望改进解锁屏幕,增减点的数目,并移动点的位置,不再是一个九宫格形状,但保持上述画线的规则不变。请计算新的解锁屏幕上,一共有多少满足规则的画线方案。

    输入输出格式

    输入格式:

    输入文件第一行,为一个整数n,表示点的数目。

    接下来n 行,每行两个空格分开的整数$x_i$ 和$y_i$,表示每个点的坐标。

    输出格式:

    输出文件共一行,为题目所求方案数除以100000007 的余数。

    输入输出样例

    输入样例#1: 复制
    4
    0 0
    1 1
    2 2
    3 3
    输出样例#1: 复制
    8
    输入样例#2: 复制
    4
    0 0
    0 1
    0 2
    1 0
    输出样例#2: 复制
    18

    说明

    样例#1解释: 设4 个点编号为1到4,方案有1->2->3->4,2->1->3->4,3->2->1->4,2->3->1->4,及其镜像4->3->2->1,3->4->2->1,2->3->4->1,3->2->4->1。

    对于30%的数据,$1≤n≤10$

    对于100%的数据,$-1000≤x_i,y_i≤1000,1≤n<20$。各点坐标不相同

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。