ID: 28

Difficulty: 3

题目描述

塔子哥最近沉迷于设计一个二维平面音游。

在我们所给的例子里，假设有24个方块，分为水平8个和垂直3个(如下表格所示)。

当玩家点击一个亮起的方块时，它周围的所有方块都会高亮。为了实现这个互动功能，塔子哥提出了一个方块组的概念：一个方块的方块组是指在上下左右方向上紧挨着的所有方块和它自己。而且垂直方向上的方块是首尾相连的，但水平方向上的方块是首尾不连的。

比如，在48个方块中，方块0的方块组是“16 8 1 0”，方块10的方块组是“2 9 18 11 10”，方块23的方块组是“15 22 7 23”。如下图所示，为了方便理解，我们把最后一行方块复制一份到第一行，表示上下相连：

16	17	18	19	20	21	22	23
0	1	2	3	4	5	6	7
8	9	10	11	12	13	14	15
16	17	18	19	20	21	22	23

塔子哥想要当玩家点击某个方块时，这个方块的整个方块组都会亮起。为了实现这个互动功能，他想让你设计一个程序，它能实时得到某个方块的方块组。

输入描述

第一行输入为3个正整数 $H$ , $V$ ( $1\leq H,V \leq 256$ )和 $M$ ( $1 \leq M < H\times V$ ), $H$ ， $V$ 为方块盘的水平个数和垂直个数；

接下来 $M$ 行，每一行输入一个方块的 $ID$ ，方格 $ID$ 从0开始，不超过 $H\times V - 1$ 如:

8 3 1
12

输出描述

输出对应的方格组，方格组内 $ID$ 以空格分隔，ID从上方起始，逆时针排列，输入的方格 $ID$ 放最后，如上例子对应的输出结果为： “4 11 20 13 12”

样例1

样例输入

12 4 1
21

输出

9 20 33 22 21

样例2

样例输入

16 4 2
0
21

样例输出

48 16 1 0
5 20 37 22 21

题目描述：塔子哥正在设计一个二维平面音游，其中有一个由 (H) 个水平方块和 (V) 个垂直方块组成的网格。每个方块的方块组是指与该方块相邻的所有方块及它自己，垂直方向的方块是首尾相连的。给定一个方块的 (ID)，要求输出该方块组中的所有方块 (ID)，并按照从上到下、逆时针排列的顺序，最后输出的方块 (ID) 放在组的末尾。

输入格式：第一行包含三个正整数 (H), (V), (M)。接下来的 (M) 行，每行输入一个方块的 (ID)。

输出格式：对于每个输入的方块 (ID)，输出对应的方块组，方块 (ID) 以空格分隔。

思路

在这个问题中，我们需要处理的是一个由 ( n ) 行和 ( m ) 列组成的网格，方块的 ID 从 0 到 ( n × m - 1 )。我们的任务是为每个给定的方块 ID 计算它的方块组，即它自己及其周围的方块 ID。

是否构图

首先，我们观察到，给定 ( n ) 和 ( m ) 后，整个图形的结构是固定的。也就是说，方块的相对位置不随时间改变，因此我们不需要动态地构建整个网格，只需通过数学运算来定位方块及其邻居。

如何查询

对每个方块 ID ( x ) 的处理逻辑如下：

垂直方向：
- 上方方块的 ID 可以表示为 ( x - n )，下方方块的 ID 表示为 ( x + n )。
- 由于垂直方向上是首尾相连的，我们可以通过对 ( x - n ) 和 ( x + n ) 进行调整来处理边界情况。具体来说：
  - 如果 ( x - n < 0 )，则我们需要加上 ( n × m )。
  - 如果 ( x + n >= n × m )，则我们需要减去 ( n × m )。
- 为了简化这些操作，我们可以直接将这两个表达式加上 ( n × m )，再取模 ( n × m ) 来确保结果在有效范围内。
水平方向：
- 水平方向的处理相对简单，因为它并不是首尾相连的。我们只需检查 ( x - 1 ) 和 ( x + 1 ) 是否在合法范围内：
  - ( x - 1 ) 必须检查 ( x ) 是否在当前行的最左侧（即 ( x % n != 0 )）。
  - ( x + 1 ) 必须检查 ( x ) 是否在当前行的最右侧（即 ( (x + 1) % n != 0 )）。

时间复杂度分析

对于每个方块 ID 的查询，我们的算法在常数时间内 ( O(1) ) 计算出它的方块组。由于需要处理 ( k ) 个查询，总的时间复杂度为 ( O(k) )。

代码

CPP

#include <bits/stdc++.h>
using namespace std;
int n, m, k;
int main(){
    cin >> n >> m >> k;//输入
    for(int i = 0; i < k; i++){
        int x;
        cin >> x;//输入询问ID
        cout << (x - n + n * m) % (n * m) << " ";//输出ID上方的数字
        if(x % n != 0)cout << x - 1 << " ";//输出ID左方的数字
        cout << (x + n + n * m) % (n * m) << " ";//输出ID下方的数字
        if((x + 1) % n != 0)cout << x + 1 << " ";//输出ID右方的数字
        cout << x << endl; //输出ID
    }
}

python

n, m, k = map(int, input().split())#输入

for _ in range(k):
    x = int(input())#输入询问ID
    print((x - n + n * m) % (n * m), end=" ")#输出ID上方的数字
    if x % n != 1:
        print(x - 1, end=" ")#输出ID左方的数字
    print((x + n + n * m) % (n * m), end=" ")#输出ID下方的数字
    if (x + 1) % n != 0:
        print(x + 1, end=" ")#输出ID右方的数字
    print(x)#输出ID

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();//输入
        int m = scanner.nextInt();
        int k = scanner.nextInt();

        for (int i = 0; i < k; i++) {
            int x = scanner.nextInt();//输入询问ID
            System.out.print((x - n + n * m) % (n * m) + " ");//输出ID上方的数字
            if (x % n != 1) {
                System.out.print(x - 1 + " ");//输出ID左方的数字
            }
            System.out.print((x + n + n * m) % (n * m) + " ");//输出ID下方的数字
            if ((x + 1) % n != 0) {
                System.out.print(x + 1 + " ");//输出ID右方的数字
            }
            System.out.println(x);//输出ID
        }
    }
}

Go

package main

import "fmt"

func main() {
    var n, m, k int
    fmt.Scan(&n, &m, &k)//输入

    for i := 0; i < k; i++ {
        var x int
        fmt.Scan(&x)//输入询问ID
        fmt.Printf("%d ", (x-n+n*m)%(n*m))//输出ID上方的数字
        if x%n != 1 {
            fmt.Printf("%d ", x-1)//输出ID左方的数字
        }
        fmt.Printf("%d ", (x+n+n*m)%(n*m))//输出ID下方的数字
        if (x+1)%n != 0 {
            fmt.Printf("%d ", x+1)//输出ID右方的数字
        }
        fmt.Println(x)//输出ID
    }
}

Js

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

rl.on('line', (line) => {
    const [n, m, k] = line.trim().split(' ').map(Number);//输入
    for (let i = 0; i < k; i++) {
        rl.on('line', (x) => {
            x = Number(x);//输入询问ID
            process.stdout.write(((x - n + n * m) % (n * m)) + ' ');//输出ID上方的数字
            if (x % n !== 1) {
                process.stdout.write((x - 1) + ' ');//输出ID左方的数字
            }
            process.stdout.write(((x + n + n * m) % (n * m)) + ' ');//输出ID下方的数字
            if ((x + 1) % n !== 0) {
                process.stdout.write((x + 1) + ' ');//输出ID右方的数字
            }
            console.log(x);//输出ID
        });
    }
});

#P1564. 2023.05.17-暑期实习-第一题-方格音游

2023.05.17-暑期实习-第一题-方格音游