当前位置：首页 > news >正文

移动二维矩阵

news 2025/5/11 7:57:06

1、题目描述

小红获得了一个 n行 m 列的二维字符矩阵，现在她要对这个字符矩阵进行向左循环移位。
向左循环移位规则如下：每一行的每一个字母(除了第一个字母)都向左边移动一位。第一行第一个的字母移动到最后一行的最后一个位置，其它行的第一个字母移动到上一行的最后一个位置。例如:
abc
def
ghi
向左循环移位一次之后的结果是
bcd
efg
hia
现在小红总共有q次询问，每次询问包含三个正整数 a,b,c，表示的问题是：原字符矩阵向左循环移位a次之后，第b行第c列的字符是什么?

输入描述:

输入第一行包含三个正整数n,m,q，分别表示二维矩阵的行数和列数，以及询问的总数。
接下来n 行，每行给出一个仅包含小写字母的字符串，长度为m，
接下来 q行，每行给出 a，b，c三个正整数。
1<=n x m<10000
1 <=n,m,q,a <= 10000
1<=b<=n
1<=c<=m

输出描述:

对于每一次询问，输出一个字符表示答案。

输入:

3 3 2
abc
edf
ghi
1 1 1
2 2 2

输出:

b
g

2、解题思路

问题分析：我们需要对字符矩阵进行多次向左循环移位，每次移位遵循特定规则：
- 每行的第一个字符移动到上一行的最后一个位置（第一行移动到最后一行的最后一个位置）。
- 其余字符向左移动一位。
预计算所有移位状态：由于移位操作具有周期性（n*m次移位后恢复原状），我们可以预先计算所有可能的移位状态，这样每次查询时可以直接获取结果。
高效查询：对于每个查询，计算有效移位次数（取模n*m），然后直接从预计算的移位矩阵中获取结果。

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 q = scanner.nextInt();scanner.nextLine(); // 读取输入后的换行符// 读取原始矩阵char[][] matrix = new char[n][m];for (int i = 0; i < n; i++) {String line = scanner.nextLine().trim();for (int j = 0; j < m; j++) {matrix[i][j] = line.charAt(j);}}// 预计算所有可能的移位状态char[][][] shiftedMatrices = new char[n * m + 1][n][m];shiftedMatrices[0] = matrix; // 初始状态为原始矩阵for (int shift = 1; shift <= n * m; shift++) {char[][] prev = shiftedMatrices[shift - 1]; // 前一次的移位结果char[][] current = new char[n][m]; // 当前移位结果// 处理第一行的第一个字符：移动到最后一行的最后一个位置current[n - 1][m - 1] = prev[0][0];// 处理其他行的第一个字符：移动到上一行的最后一个位置for (int i = 1; i < n; i++) {current[i - 1][m - 1] = prev[i][0];}// 处理其余字符：向左移动一位for (int i = 0; i < n; i++) {for (int j = 1; j < m; j++) {current[i][j - 1] = prev[i][j];}}shiftedMatrices[shift] = current; // 保存当前移位结果}// 处理每个查询for (int i = 0; i < q; i++) {int a = scanner.nextInt(); // 移位次数int b = scanner.nextInt(); // 行号（1-based）int c = scanner.nextInt(); // 列号（1-based）// 计算有效移位次数（考虑周期性）int effectiveShift = a % (n * m);// 从预计算的移位矩阵中获取结果字符char result = shiftedMatrices[effectiveShift][b - 1][c - 1];System.out.println(result);}}
}