← 返回题目列表

AtCoder · APG4b_t

T. 2.03.多维数组

中文机器翻译题面 查看原题
page_url:https://atcoder.jp/contests/apg4b/tasks/APG4b_t

上一页 | 下一页

要点

  • 2次元配列在处理二维表时很有用 可以用
  • vector<vector<要素の型>> 変数名(要素数1, vector<要素の型>(要素数2, 初期値))声明
  • 初始值可以省略 您可以使用
  • 変数名.at(i).at(j)访问第 i 行和第 j 列 您可以使用
  • 変数名.size()获取垂直尺寸 您可以使用
  • 変数名.at(0).size()获取水平尺寸
  • 指定和初始化元素的示例
vector<vector<int>> data = {
  {7, 4, 0, 8},
  {2, 0, 3, 5},
  {6, 1, 7, 0},
};
  • 具有 2 个或更多维度的数组多次元配列这就是所谓的
  • 嵌套的 N 个向量称为 N 维数组。

数组是处理“数据列”的函数。
此页面包含处理“数据表”时的有用信息。 2次元配列,更高的维度 引入一个名为 多次元配列 的数组。

2次元配列

让我们看看下面的问题。

例題

有一个表格,其中的整数写成垂直 3 行、水平 4 列。求这个表中有多少个 0。 以下是

表的示例。

7 4 0 8
2 0 3 5
6 1 7 0
入力
7 4 0 8
2 0 3 5
6 1 7 0
実行結果
3

当将这样的数据表处理为二维数组时,可以如下编写。

#include <bits/stdc++.h>
using namespace std;

int main() {

  // int型の2次元配列(3×4要素の)の宣言
  vector<vector<int>> data(3, vector<int>(4));

  // 入力 (2重ループを用いる)
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 4; j++) {
      cin >> data.at(i).at(j);
    }
  }

  // 0の個数を数える
  int count = 0;

  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 4; j++) {

      // 上からi番目、左からj番目の画素が0かを判定
      if (data.at(i).at(j) == 0) {
        count++;
      }

    }
  }

   cout << count << endl;

}

宣言

二维数组的声明采用以下形式:

vector<vector<要素の型>> 変数名(要素数1, vector<要素の型>(要素数2, 初期値));
vector<vector<要素の型>> 変数名(要素数1, vector<要素の型>(要素数2));  // 初期値を省略

初始值可以省略。如果省略,它将使用与“元素类型”相对应的零值进行初始化。
例如,如果元素类型是int,初始值为0在,string是一个空字符串("")。

处理类似表格的数据时,通常会执行以下操作:

vector<vector<要素の型>> 変数名(縦の要素数, vector<要素の型>(横の要素数));

示例中处理的数据是

  • 元素是整数
  • 3 条垂直线
  • 水平 4 行 由于它是

的表,因此声明如下。

vector<vector<int>> data(3, vector<int>(4));

访问

要访问二维数组的元素,请按如下方式编写。

変数名.at(添字1).at(添字2)

声明时vector<vector<要素の型>> 変数名(縦の要素数, vector<型>(横の要素数)),那么更具体地说:

変数名.at(上から何番目か).at(左から何番目か)

示例中,在输入部分,要输入“从上数第i个元素,从左数第j个元素”, 写入

cin >> data.at(i).at(j)

。
另外,判断从上数第i个格子和从左数第j个格子是否为0,

if (data.at(i).at(j) == 0)

。

获取尺寸

vector<vector<int>> data(3, vector<int>(4));

data.size();  // 3 (縦の要素数) (12ではないことに注意!)
data.at(0).size();  // 4 (横の要素数)

获取垂直元素的数量 获取水平元素的数量为変数名.size()比方说変数名.at(0).size()。 请注意,当您使用

変数名.size()时,返回的是垂直元素的数量,而不是所有元素的数量。
当你需要所有元素数量时 必须使用縦の要素数 * 横の要素数找到它。

二维数组的概念

为了便于解释,我们将迄今为止所处理的普通数组称为“一维数组”。

让我们回顾一下一维数组。由“初始值”和“元素数量”组成的数组声明如下。 (1.13 配列(查看详情) TODO:我希望能够直接跳转到链接部分

vector<要素の型> 変数名(要素数, 初期値);

二维数组是““一维数组”的数组我认为这样更容易理解。

如何声明二维数组

表示一维数组的类型是 这是vector<要素の型>。
表示二维数组的类型是“一维数组”的数组,因此vector<vector<要素の型>>。 (“外部数组的元素类型”是表示一维数组的类型。)
另外,由于二维数组的“初始值”是“一维数组”vector<vector<要素の型>> 変数名(要素数1, 初期値)的“初始值”部分是 指定vector<要素の型>(要素数2))。 (它是一个由“2”个元素组成的一维数组。) 访问

元素可以被认为如下。

変数名.at(i)  // i番目の1次元配列
変数名.at(i).at(j)  // i番目の1次元配列 のj番目の要素

对于某些人来说,用“从顶部开始的数字”和“从左边开始的数字”来表达二维数组的下标可能不太直观,但已经习惯了。最好记住垂直 x 水平。
示例输入和数组下标的对应关系如下表所示。

i\j 0 1 2 3
0 7 4 0 8
1 2 0 3 5
2 6 1 7 0

输入此数据时请考虑以下元素。

  • data.at(0).at(1)
  • data.at(1).at(3)
  • data.at(2).at(2)

答案

  • data.at(0).at(1) → 4 (第 0 个一维数组的第一个元素)
    第 0 个一维数组是 {7, 4, 0, 8} 。

  • data.at(1).at(3) → 5 (第一个一维数组的第三个元素)
    第一个一维数组是 {2, 0, 3, 5} 。

  • data.at(2).at(2) → 7 (第二个一维数组的第二个元素)
    第二个一维数组是 {6, 1, 7, 0} 。


N×0的二维数组

稍后向数组添加和使用元素时, 您可以声明一个N×0数组。

如果你写成如下, 它将是一个N×0的二维数组。

vector<vector<型>> 変数名(N);  // 「要素数0の配列」の配列

外面 通过省略vector的初始值, 每个N数组中的元素数量为 0。


非矩形的二维数组(锯齿数组) 稍后向

N×0二维数组添加元素时,可能会创建“每行元素数量不同的二维数组”。
这样的数组有时称为锯齿状数组。

具体例

下面data是锯齿状数组的示例。 下面显示了

vector<vector<int>> data(3);  // 3×0の配列

data.at(0).push_back(1);
data.at(0).push_back(2);
data.at(0).push_back(3);
// data.at(0)は3要素の配列

data.at(1).push_back(4);
data.at(1).push_back(5);
data.at(1).push_back(6);
data.at(1).push_back(7);
// data.at(1)は4要素の配列

data.at(2).push_back(8);
data.at(2).push_back(9);
// data.at(2)は2要素の配列

data的图像。


多次元配列

二维数组可以进一步扩展以创建更高维的数组,例如三维和四维数组。
合并维度大于 1 维的数组多次元配列。

让我们看一个使用 3D 数组的示例。

例題

游戏状态为 给出了N。圆用“o”表示,十字用“x”表示,空格用“-”表示。求所有州中“o”的数量之和。

第一状态

- - -
- x -
- o -

第二状态

x o -
- o -
x - -
入力
2
- - -
- x -
- o -

x o -
- o -
x - -
実行結果
3
#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;
  // N × (3 × 3)要素の配列を宣言
  vector<vector<vector<char>>> data(N, vector<vector<char>>(3, vector<char>(3)));

  // 入力
  for (int i = 0; i < N; i++) {
    // i番目の状態を読む
    for (int j = 0; j < 3; j++) {
      for (int k = 0; k < 3; k++) {
        cin >> data.at(i).at(j).at(k);
      }
    }
  }

  // 'o'の数を数える
  int count = 0;

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < 3; j++) {
      for (int k = 0; k < 3; k++) {

        // 「i番目の状態」「上からj番目」「左からk番目」の要素が'o'か判定
        if (data.at(i).at(j).at(k) == 'o') {
          count++;
        }

      }
    }
  }

   cout << count << endl;
}

三维或更多维的数组几乎与二维数组相同。

宣言

3维数组的声明方法如下所示。

vector<vector<vector<要素の型>>> 変数名(要素数1, vector<vector<要素の型>>(要素数2, vector<要素の型>(要素数3, 初期値)));
vector<vector<vector<要素の型>>> 変数名(要素数1, vector<vector<要素の型>>(要素数2, vector<要素の型>(要素数3)));  // 初期値を省略

这可能看起来很可怕,但基本思想与二维数组相同。
将三维数组视为二维数组的数组,或一维数组的数组。我将添加换行符以使其更易于理解。

vector<
  vector<vector<要素の型>> /* 2次元配列の型 */
> 変数名(要素数1,
  vector<vector<要素の型>>(要素数2, vector<要素の型>(要素数3, 初期値)) /* 2次元配列の値 */
);

对于 4 个或更多维度,以相同的方式声明。让我们将 N 维数组视为“N-1 维数组”的数组。

访问

要访问 N 维数组的元素,请编写:

変数名.at(添字1).at(添字2).at(添字3) ... .at(添字N)

重复 .at(下标) N 次。


注意点

处理多维数组时的基本注意事项与处理一维数组时相同。

在多维数组中,请注意下标的顺序。
另外,変数名.size()允许您获取第一维中元素的数量,但请注意,您无法获取所有元素的数量。

vector<vector<vector<int>>> data = {
  {
    {1, 2, 3, 4},
    {5, 6, 7, 8},
    {9, 10, 11, 12},
  },
  {
    {13, 14, 15, 16},
    {17, 18, 19, 20},
    {21, 22, 23, 24},
  },
};

int size1 = data.size();
cout << size1 << endl;  // 2

int size2 = data.at(0).size();
cout << size2 << endl;  // 3

int size3 = data.at(0).at(0).size();
cout << size3 << endl;  // 4

cout << size1 * size2 * size3 << endl;  // 24

详细信息

指定并初始化元素

// 2次元配列の初期化
vector<vector<int>> data1 = {
  {7, 4, 0, 8},
  {2, 0, 3, 5},
  {6, 1, 7, 0}
};

// 3次元配列の初期化
vector<vector<vector<char>>> data2 = {
  {
    {'-', '-', '-'},
    {'-', 'x', '-'},
    {'-', 'o', '-'}
  },
  {
    {'x', 'o', '-'},
    {'-', 'o', '-'},
    {'x', '-', '-'}
  }
};

如果预先确定了元素的值和大小,则可以指定并初始化该元素。

将一维数组用作多维数组

我们介绍过,当您想要处理“数据表”时,多维数组是合适的。然而,“数据表”可以被视为“数据列”,将其“拉平”为单列,因此也可以将其视为一维数组。

将二维表转换为一维的方法有很多种,但最简单的方法是将表分为行并将其转换为一维列:“第 1 列数据→第 2 列数据→第 3 列数据→...”。
例如,当要处理一个纵向H行、横向W列的表格时,数据数量为H×W,所以 可以表示为vector<型> 変数名(H * W);。在这种情况下,当访问从顶部算起的第 y 个元素和从左侧算起的第 x 个元素时,変数名.at(y * W + x)。 请注意,当您使用

y * W部分表示目标元素所在行的开头位置。由于一行中的数据是按行排列的,所以要获取第x列的数据,它位于行首前面x的位置。

(0, 0) (0, 1) (0, 2)
(1, 0) (1, 1) (1, 2)
(2, 0) (2, 1) (2, 2)

使用向量以外的东西的多维数组

正如我在《1.13 数组》的详细介绍中所介绍的,除了向量之外,C++ 中还有其他表示数组的方式。

vector<int> data(3); // vectorによる要素数3の配列
int data[3]; // Cの要素数3の配列
array<int, 3> data; // arrayによる要素数3の配列

本页介绍了使用向量的多维数组,但多维数组也可以使用向量以外的数组来表示。

// vector を用いた2次元配列
vector<vector<int>> data(3, vector<int>(4));  // 縦3 x 横4 の2次元配列
data.at(1).at(2)  // 上から2番目、左から3番目の要素へのアクセス (1番目から数えていることに注意)

// array を用いた2次元配列
array<array<int, 4>, 3> data = {};  // 縦3 × 横4 の2次元配列
data.at(1).at(2)  // 上から2番目、左から3番目の要素へのアクセス

// Cの配列を用いた2次元配列
int data[3][4] = {};  // 縦3 × 横4 の2次元配列
data[1][2]  // 上から2番目、左から3番目の要素へのアクセス

需要注意的是,数组和 C 数组不能使用变量来表示元素的数量,并且对于 C 数组,越界访问不会导致错误,但会引入错误。在您习惯之前,请尝试使用向量多维数组。

## 不使用 at 访问元素 使用 C++ 向量的数组可以使用“数组变量.at(下标)”进行访问,但也可以按照 C 语言数组的形式写为“数组变量 [下标]”。对于二维数组也是如此;您可以编写“数组变量 [下标 1][下标 2]”,而不是编写“数组变量.at(下标 1).at(下标 2)”。 但是,以“数组变量 [下标 1] [下标 2]”的形式进行访问可能不会导致错误,并且如果指定了范围之外的下标,则可能会出现意外行为。当使用带有“[]”符号的访问时,必须非常小心,不要指定超出范围的下标。 在您习惯之前,使用“.at”访问是安全的。

問題

请解决链接目的地的问题。

EX18.游戏锦标赛

ABC问题链接

ABC问题

我们将介绍AtCoder初学者大赛的过去问题,可以用到目前为止的知识来解决。如果您对练习题不满意,请尝试一下。

#### 简单 #### 困难

ABC107 B - 网格压缩

vector<string> 感觉不像多维数组。

上一页 | 下一页

## 注意 二维数组的具体例子和乐趣 → 如何使用二维数组(→ 二维数组是数组的数组) → 多维数组 → 初始化 TODO:编写矢量版本 有点奇怪的是,在使用它作为参数时必须指定一个元素(尽管您可以省略第一个元素) 是否可以用AtCoder判断最后一个空格是否正确? 练习题强制数组是有必要的,但是不需要例子吗? 你有这个吗? >在普通数组(一维数组)中处理这样的数据有点麻烦。 你有这个吗? >最好将二维数组的下标记为“从顶部开始的数字”- 垂直 x 水平。 我是否应该包含“二维数组通常与双循环一起使用”之类的声明? 解释“如果它是一个 C 数组,那么二维数组就是数组的数组”这样的事情太难了。最好以编程方式显示向量版本实际上是数组的数组。 最好不要使用“下标n”这个表达方式?有道理吗? if语句中使用了nest这个词,但是是不是很难理解呢? > “结果是一个与维数一样多的嵌套‘{}’。” 流量是突然的吗? >“多维数组通常很难可视化。”