type
status
date
slug
summary
tags
category
icon
password
链接：‣
题目描述
mutsumi有两个排列，放置在一个的矩形中，每次你可以选择一个数字，将两个排列内的所在的单元格删除。
mutsumi想删除尽可能少的数字，使得矩形至少被分成两个连通块（不一定是矩形），请输出最小的删除次数。若无法通过删除使得矩形被分成至少两个连通块，则输出 -1。
连通块：块内任意两点（可以是同一点）都可以找到至少一条只由上下左右组成的路径相连。
长度为的排列为：中，每个数字恰好出现一次。
输入描述:
第一行输入一个整数表示测试数据组数。
每组测试数据的第一行输入一个整数表示排列长度。
每组测试数据的第二行输入个整数表示第一个排列。
每组测试数据的第三行输入个整数表示第二个排列。
的总和不超过。
输出描述:
输出一个整数表示答案。无解则输出。
示例1
输入
输出
说明
第一组数据中，无法通过删除使得矩形至少被分成两个连通块，因此输出。第二组数据中，删除数字，即可将矩形分成两个连通块。
题解
因为只有两行，所以结果只有三种，-1、1或2。按照题意，我们只需要对其进行分类讨论即可。
- 排列长度等于2：
(1)如果，此时结果为1。
(2)如果，此时无解，输出-1。
- 排列长度大于2：
(1)存在，且，则操作一次即可，输出1。
(2)存在或者，且均不越界，则操作一次即可，输出1。
(3)不符合上述情况，则需要操作两次，输出2。
- 排列长度等于2，即长度为1：
(1)无解，输出-1。
完整代码如下：
- Author:Serendipity
- URL:https://serendipity565.netlify.app//article/mutsumi%E7%9A%84%E6%8E%92%E5%88%97%E8%BF%9E%E9%80%9A
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!