P3341 [ZJOI2014]消棋子

    • 16通过
    • 124提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 枚举,暴力 模拟 队列 2014 浙江 高性能
  • 难度 省选/NOI-
  • 时空限制 5000ms / 256MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    消棋子是一个有趣的游戏。游戏在一个r * c的棋盘上进行。棋盘的每个格子,要么是空,要么是一种颜色的棋子。同一种颜色的棋子恰好有两个。

    每一轮,玩家可以选择一个空格子(x, y),并选择上下左右四个方向中的两个方向,如果在这两个方向上均存在有棋子的格子,而且沿着这两个方向上第一个遇到的棋子颜色相同,那么,我们将这两个棋子拿走,并称之为合法的操作。否则称这个操作不合法,游戏不会处理这个操作。游戏的目的是消除尽量多的棋子。

    给出这样一个游戏和一个人的玩法。你需要: z 指出此人能消去多少棋子。 z 给出一种能消去最多棋子的方案。

    输入输出格式

    输入格式:

    第一行给出了整数r, c。第二行给出了整数n,表示不同颜色数。接下来n行,第i行含4个整数a[i], b[i], c[i], d[i],表示颜色为i的两个格子分别是(a[i], b[i]), (c[i], d[i])。然后是一个整数m,表示此人的操作数。接下来m行,每行有2个整数和2个字母,代表了他选择的格子,以及两个方向。我们用”UDLR“分别表示上下左右。

    输出格式:

    第一行输出此人能消去多少棋子。第二行含一个整数k(0 <=k <=10^6),表示你给出的方案的操作数。接下来k行,每行2个整数和2个字母,代表你选择的格子以及两个方向。

    输入输出样例

    输入样例#1: 复制
    4 4
    4
    1 1 1 4
    1 2 3 4
    1 3 3 2
    4 1 2 3
    6
    2 3 U R
    2 1 D R
    2 2 L R
    2 4 L D
    3 1 L R
    3 3 L U
    输出样例#1: 复制
    2 4
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。