P4431 [COCI2017-2018#2] ​Košnja

    • 668通过
    • 955提交
  • 题目提供者 da32s1da
  • 评测方式 云端评测
  • 标签 搜索 模拟 COCI 2017 高性能
  • 难度 普及-
  • 时空限制 1000ms / 64MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    题目大意:

    给定一个$n*m$的矩阵,每次你可以选择前进一格或转弯(90度),求在不出这个矩阵的情况下遍历全部格点所需最少转弯次数。有多组数据

    输入格式:

    第一行一个整数$k$,表示数据组数

    以下$k$行,每行两个整数$n,m$,表示矩阵大小

    输出格式:

    输出一个整数,即最少转弯次数

    感谢@守望 提供翻译

    题目描述

    Mirko wants to buy land on which he will build a house for his family. So far, he’s seen K pieces of land. Each of them is in the shape of a rectangle and we can think of it as a matrix with N rows and M columns, N × M fields in total.

    Mirko is aware that, before construction begins, the property needs to be regularly maintained and the lawn needs to be mowed. Because of this, Mirko bought a lawn mower. In order to mow the entire lawn of N rows and M columns, he needs to go over each field at least once. He can start from any field facing one of the four main directions (up, down, left, and right). His lawn mower can only go forwards (to the adjacent field facing the current direction) or make a 90 degree turn. Additionally, because of his own safety, Mirko can only use the lawn mower on his land, so he cannot leave the matrix.

    Since making the lawn mower turn isn’t simple, Mirko wants to mow the lawn with the minimal amount of turns. For each piece of land he saw so far, Mirko wants to know the minimal number of turns he can make so that the entire lawn is mowed. Help Mirko solve this problem.

    输入输出格式

    输入格式:

    The first line of input contains the positive integer K (1 ≤ K ≤ 50 000), the number from the task.

    Each of the following K lines contains two positive integers N and M (1 ≤ N, M ≤ 1 000 000), the numbers from the task.

    输出格式:

    For each piece of land Mirko saw so far, output in a separate line the minimal amount of turns he can take so that the entire lawn is mowed.

    输入输出样例

    输入样例#1: 复制
    2
    1 10
    10 1
    
    输出样例#1: 复制
    0
    0
    输入样例#2: 复制
    3
    1 1
    3 3
    3 4
    
    输出样例#2: 复制
    0
    4
    4
    输入样例#3: 复制
    2
    5 8
    6 4
    输出样例#3: 复制
    8
    6

    说明

    In test cases worth 50% of total points, Mirko will see only one piece of land. The dimensions of this piece of land will be smaller than 500.

    Clarification​ ​of​ ​the​ ​first​ ​test​ ​case:

    The first piece of land can be mowed without making any turns if he starts from the field in the first column of the table, faced to the right and only going forwards. A similar idea applies for the second piece of land.

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