P4003 无限之环(infinityloop)

    • 39通过
    • 94提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 清华集训 2017 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    曾经有一款流行的游戏,叫做 Infinity Loop,先来简单的介绍一下这个游戏:

    游戏在一个 n ∗ m 的网格状棋盘上进行,其中有些小方格中会有水管,水管可能在

    格某些方向的边界的中点有接口,所有水管的粗细都相同,所以如果两个相邻方格的

    共边界的中点都有接头,那么可以看作这两个接头互相连接。水管有以下 15 种形状:

    游戏开始时,棋盘中水管可能存在漏水的地方。

    形式化地:如果存在某个接头,没有和其它接头相连接,那么它就是一个漏水的

    地方。

    玩家可以进行一种操作:选定一个含有非.直.线.型.水管的方格,将其中的水管绕方格

    中心顺时针或逆时针旋转 90 度。

    直线型水管是指左图里中间一行的两种水管。

    现给出一个初始局面,请问最少进行多少次操作可以使棋盘上不存在漏水的地方。

    输入输出格式

    输入格式:

    从文件 infinityloop.in 中读入数据。

    第一行两个正整数 n, m,代表网格的大小。

    接下来 n 行每行 m 个数,每个数是 [0,15] 中的一个,你可以将其看作一个 4 位的

    二进制数,从低到高每一位分别代表初始局面中这个格子上、右、下、左方向上是否有

    水管接头。

    特别地,如果这个数是 0 ,则意味着这个位置没有水管。

    比如 3(0011(2)) 代表上和右有接头,也就是一个 L 型,而 12(1100(2)) 代表下和左

    有接头,也就是将 L 型旋转 180 度。

    输出格式:

    输出到文件 infinityloop.out 中。

    输出共一行,表示最少操作次数。如果无法达成目标,输出-1.

    输入输出样例

    输入样例#1: 复制
    2 3
    3 14 12
    3 11 12
    输出样例#1: 复制
    2
    输入样例#2: 复制
    3 2
    1 8
    5 10
    2 4
    输出样例#2: 复制
    -1
    输入样例#3: 复制
    3 3
    9 11 3
    13 15 7
    12 14 6
    输出样例#3: 复制
    16

    说明

    【样例 1 解释】

    样例 1 棋盘如下

    旋转方法很显然,先将左上角虚线方格内的水管顺时针转 90 度

    然后右下角虚线方格内的水管逆时针旋转 90 度,这样就使得水管封闭了

    【样例 2 解释】

    样例 2 为题目描述中的第一张图片,无法达成目标。

    【样例 3 解释】

    样例 3 为题目描述中的第二张图片,将除了中心方格以外的每个方格内的水管都转 180 度即可。

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