Двумерные массивы. Матрицы

До сих пор мы рассматривали массивы атомарных (простых, неделимых) типов. Например

int a[3];       

описывает массив на 3 целочисленных элемента. Однако элементом массива может являться и другой массив. Например, объявление

int a[3][2];

приведет к созданию массива из трех элементов, каждый из которых будет массивом из 2-х элементов.

двумерный массив int a[3][2]

a[0]

a[1]

a[2]

a[0][0]

a[0][1]

a[1][0]

a[1][1]

a[2][0]

a[2][1]

байты…

…байты

Такие массивы называют двумерными. Другое распространенное название двумерных массивов – матрицы.

Матрица – это математический объект, представляющий собой прямоугольную таблицу с числами[23].

Как и обычный (одномерный) массив, матрицу удобно обрабатывать с помощью циклов. Например, если требуется записать в матрицу таблицу квадратов двузначных натуральных чисел и вывести на консоль, то это можно реализовать с помощью программы:

#include <iostream>

#include <iomanip>        //setw задает ширину данных при выводе

using namespace std;

int main(){

int a[9][10];        // объявляем двумерный массив

for (int i = 0; i < 9; i++) {        // цикл по строкам

     for (int j = 0; j < 10; j++) {  // цикл по столбцам

           a[i][j] = (i + 1) * 10 + j;

           a[i][j] *= a[i][j];

           cout << setw(6) << a[i][j];

     }

     cout << endl;

}

return 0;

}

В результате работы программы будет выведено:

100 121 144 169 196 225 256 289 324 361

400 441 484 529 576 625 676 729 784 841

900 961 1024 1089 1156 1225 1296 1369 1444 1521

1600 1681 1764 1849 1936 2025 2116 2209 2304 2401

2500 2601 2704 2809 2916 3025 3136 3249 3364 3481

3600 3721 3844 3969 4096 4225 4356 4489 4624 4761

4900 5041  5184 5329 5476 5625 5776 5929 6084 6241

6400 6561 6724 6889 7056 7225 7396 7569 7744 7921

8100 8281 8464 8649 8836 9025 9216 9409 9604 9801

Как и одномерный массив, многомерный можно сразу заполнить при инициализации:

inta[3][4] = { 1, 15, 20, 17,

           44, 1, 4, 100,

           5, 88, 0, 400};

При этом a[0][0] будет равно 1, a[0][1] получит значение 15, … a[1][0] будет присвоено 44 и т.д.

ВАЖНО: Как и в случае одномерных массивов имя (идентификатор) двухмерного (многомерного) массива в C/C++ является указателем на первый элемент массива.

Это можно проиллюстрировать следующим примером. Фрагмент программы:

int a[3][4] = { 1, 15, 20, 17, // a₀₀, a₀₁, a₀₂, a₀₃

           44, 1, 4, 100, // a₁₀, a₁₁, a₁₂, a₁₃

           5, 88, 0, 400}; // a₂₀, a₂₁, a₂₂, a₂₃

int *ptr = (int *)a;      // берём указатель на начало матрицы

cout << *(ptr + 2 *4 + 1); // выводим a[2][1] через указатель

Выведет элемент a[2][1] т.е. число 88. Величина 4 в формуле означала количество элементов в одной строке. Последнюю операцию вывода можно было использовать и в форме:

cout << ptr[2 * 4 + 1];

ВАЖНО: Матрицу, как и любой многомерный массив можно реализовать с помощью одномерного.

Например, матрицу x[4][5] можно реализовать как одномерный массив y[4*5]. А обращение к её элементу, например x[3][2], будет выглядеть как y[3*5+2].

Задача №106.  Диагонали

В квадратной таблице n × n подсчитать суммы чисел, стоящих на диагоналях.

Входные данные

Вводится число n (1 ≤ n ≤ 5000), а затем матрица n × n. Элементы матрицы – числа, по модулю не превышающие 10⁵.

Выходные данные

Вывести сумму чисел сначала на главной, а затем на побочной диагонали. Главной диагональю квадратной матрицы называется диагональ, которая проходит через верхний левый и нижний правый углы.

Пример

№	Ввод	Вывод
1	1 451	451  451
2	4 134  475  30  424 303  151  419  235 248  166  90  42 318  237  184  36	411  1327

Решение

Единственная сложность данной задачи – предполагаемый размер матрицы – 25000000 элементов. На самом деле, нет никакой необходимости хранить все эти элементы. Достаточно проверять, какой из диагоналей принадлежит элемент матрицы при его считывании.

#include <iostream>

int main() {

int n, k, sum1 = 0, sum2 = 0;

std::cin >> n;

for(int i = 0; i < n; i++)

   for(int j = 0; j < n; j++){

       std::cin >> k;

       if(i == j) sum1 += k;

       if(i == n–1-j) sum2 += k;

   }

std::cout << sum1 << " " << sum2 << "\n";

}

Рассмотрим похожую по смыслу задачу на обработку табличных данных, которую рациональнее всего решать без применения массива.

Задача №107.  MaxMin и MinMax

В таблицу размером m×nзаписаны числа, не превышающие по модулю 1000. Найдите наибольший из минимумов по всем строкам и наименьший из максимумов по всем строкам.

Входные данные

В первой строке через пробел два целых числа 1 ≤ n, m ≤ 10000 – размеры таблицы. В следующих n строках в каждой по m целых чисел, не превышающих по модулю 1000.

Выходные данные

Два числа через пробел. Первое – наибольший минимум по всем строкам, второе – наименьший максимум по всем строкам.

Решение

#include <cstdio>

int main() {

int n, m, k, maxmin = -1001, minmax = 1001, mn, mx, i;

scanf("%d%d", &n, &m);

while(n--) {

   mn = 1001; mx = -1001; i = m;

   while(i--) {

       scanf("%d", &k);

       if(k < mn) mn = k;

       if(k > mx) mx = k;

   }

   if (mx < minmax) minmax = mx;

   if (mn > maxmin) maxmin = mn;

}

printf("%d %d", maxmin, minmax);

}

Задача №108.  Проверка на симпатичность(acmp.ru)

 (Время: 1 сек. Память: 16 Мб)

Рассмотрим таблицу, содержащую n строк и m столбцов, в каждой клетке которой расположен ноль или единица. Назовем такую таблицу симпатичной, если в ней нет ни одного квадрата 2 на 2, заполненного целиком нулями или целиком единицами.

Так, например, таблица 4 на 4, расположенная слева, является симпатичной, а расположенная справа таблица 3 на 3 - не является.

1	0	1	0		0	0	1
1	1	1	0		0	0	1
0	1	0	1		1	1	1
0	0	0	0

Задано несколько таблиц. Необходимо для каждой из них выяснить, является ли она симпатичной.

Входные данные

Первая строка входного файла INPUT.TXT содержит количество t (1 ≤ t ≤ 10) наборов входных данных. Далее следуют описания этих наборов. Описание каждого набора состоит из строки, содержащей числа n и m (1 ≤ n, m ≤ 100), и n строк, каждая из которых содержит по m чисел, разделенных пробелами. j-ое число в i+1 - ой строке описания набора входных данных - элемент aij соответствующей таблицы. Гарантируется, что все a_ij равны либо нулю, либо единице.

Выходные данные

Для каждого набора входных данных выведите в файл OUTPUT.TXT единственную строку, содержащую слово «YES», если соответствующая таблица является симпатичной, и слово «NO» - в противном случае.

Пример

INPUT.TXT	OUTPUT.TXT
3 1  1 0 4  4 1  0  1  0 1  1  1  0 0  1 0  1 0  0  0  0 3  3 0  0  1 0  0  1 1  1  1	YES YES NO

Решение

Очевидно, что в квадрате, который делает таблицу «несимпатичной» сумма может быть либо равна 4 либо равна 0.

#include <fstream>

#define SIZE 101

#define SQUARE (a[i][j] + a[i-1][j] + a[i][j-1] + a[i-1][j-1])

using namespace std;

int t, n, m, a[SIZE][SIZE], i, j, tmp;

bool ans;

int main() {

ifstream cin("input.txt");

ofstream cout("output.txt");

cin >> t;

while(t--){

   cin >> n >> m;

   ans = true;

   for(i = 0; i < n; i++)

       for(j = 0; j < m; j++){

           cin >> a[i][j];

           if(i && j){

               tmp = SQUARE % 4;

               if(!tmp) ans = false;

           }

       }

   cout << (ans ? "YES" : "NO") << endl;

}

}

Задача №109.  Табло

На хоккейном стадионе в одном большом городе расположено большое прямоугольное табло. Оно имеет n строк и m столбцов (то есть состоит из n × m ячеек). Во время хоккейного матча это табло служит для отображения счета и времени, прошедшего с начала тайма, а в перерывах на нем показывают различную рекламу.

В связи с этим возникла задача проверки возможности показа на этом табло определенной рекламной заставки. Заставка также, как и табло, имеет размер n строк на m столбцов. Каждая из ячеек заставки окрашена в один из четырех цветов - трех основных: красный - R, зеленый - G, синий - B и черный - .(точка).

Каждая из ячеек табло характеризуется своими цветопередаточными возможностями. Любая из ячеек табло может отображать черный цвет - это соответствует тому, что на нее вообще не подается напряжение. Также каждая из ячеек может отображать некоторое подмножество множества основных цветов. В этой задаче эти подмножества будут кодироваться следующим образом:

· 0 - ячейка может отображать только черный цвет;

· 1 - ячейка может отображать только черный и синий цвета;

· 2 - ячейка может отображать только черный и зеленый цвета;

· 3 - ячейка может отображать только черный, зеленый и синий цвета;

· 4 - ячейка может отображать только черный и красный цвета;

· 5 - ячейка может отображать только черный, красный и синий цвета;

· 6 - ячейка может отображать только черный, красный и зеленый цвета;

· 7 - ячейка может отображать только черный, красный, зеленый и синий цвета.

Напишите программу, которая по описанию табло и заставки определяет,можно ли на табло отобразить эту заставку.

Входные данные

Первая строка входного файла INPUT.TXT содержит целые числа n и m (1 ≤ n, m ≤ 100). Далее идут n строк по m символов каждая - описание заставки. Каждый из символов описания заставки принадлежит множеству {R, G, B, .} . Их значения описаны выше.

После этого идет описание табло. Оно содержит n строк по m чисел, разделенных пробелами. Значения чисел описаны выше.

Выходные данные

В выходной файл OUTPUT.TXT выведите YES, если на табло можно отобразить заставку и NO - в противном случае.

Примеры

№	INPUT.TXT	OUTPUT.TXT
1	3  3 .GB R.B RG. 0  1  2 3  4  5 6  7  0	NO
2	2  3 RGB .G. 7  7  7 7  7  7	YES

Решение

#include <fstream>

using namespace std;

char p[100][100], ch;

int main() {

ifstream cin("input.txt");

ofstream cout("output.txt");

int n, m, cell, r, g, b;

cin >> n >> m;

for (int i = 0; i < n; i++)

   for (int j = 0; j < m; j++)

       cin >> p[i][j];

for (int i = 0; i < n; i++)

   for (int j = 0; j < m; j++){

       cin >> cell;

       r = cell / 4;

       g = cell / 2 % 2;

       b = cell % 2;

       ch = p[i][j];

       if(ch=='B' && !b || ch=='G' && !g || ch=='R' && !r){

           cout << "NO";

           return 0;

       }

   }

cout << "YES";

}

Задача №110.  Морской бой

Наверно нет школьника, который хотя бы раз не играл в «Морской бой». Квадратное игровое поле размера N×N состоит из клеток, каждая из которых может быть либо свободной, либо занятой кораблём. Размеры кораблей могут быть от 1×1 до 1×K или от 1×1 до K×1 клеток. Как правило, K=4. Корабли не могут касаться сторонами, либо соприкасаться углами. Определите по описанию игрового поля, сколько на нем кораблей.

Входные данные

В первой строке единственное натуральное число N ≤ 100 – размер игрового поля.

В следующих N строках ровно по N чисел, записанных через пробел – описания клеток. Занятая клетка обозначается единицей, а свободная – нулем.

Выходные данные

Единственное число – количество кораблей на игровом поле.

Пример

Ввод	Вывод
8 1 1  1  0  0  0 0 1 0 0 0 0 1 0 0 1 1 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1	9

Пояснение к примеру - в данном случае игровое поле выглядит следующим образом

Решение

Очевидно, у каждого корабля есть только один левый верхний угол – клетка, соседи которой слева и сверху либо свободны, либо не существуют.Определив количество таких клеток на поле, мы узнаем количество кораблей.

 

#include <iostream>

#define SIZE 100

int a[SIZE][SIZE] = {0,}, n, cnt = 0;

int main(){

std::cin >> n;

for(int i = 0; i < n; i++)

   for(int j = 0; j < n; j++){

       std::cin >> a[i][j];

       cnt += a[i][j] && (i && !a[i-1][j] || !i)

                      && (j && !a[i][j-1] || !j);

}

std::cout << cnt;       

}

Задача №111.  Седловые точки (acmp.ru)

(Время: 1 сек. Память: 16 Мб)

Задана матрица, содержащая N строк и M столбцов. Седловой точкой этой матрицы назовем элемент, который одновременно является минимумом в своей строке и максимумом в своем столбце.

Найдите количество седловых точек заданной матрицы.

Входные данные

Входной файл INPUT.TXT в первой строке содержит целые числа N и M (1 ≤ N, M ≤ 750). Далее следуют N строк по M чисел в каждой. Элементы матрицы - целые числа, не превосходящие 1000 по абсолютной величине.

Выходные данные

В выходной файл OUTPUT.TXT выведите ответ на задачу.

Примеры

№	INPUT.TXT	OUTPUT.TXT
1	2  2 0  0 0  0	4
2	2  2 1  2 3  4	1

Решение

Главную сложность в задаче составляет большой объем вводимых данных. Для ускорения обработки используем библиотеку stdio вместо потоковой обработки. Однако этого недостаточно. Если для каждого элемента матрицы проверять, является ли он седловой точкой при помощи двух циклов, это также займет много времени. Воспользуемся двумя вспомогательными одномерными массивами, в которых будем хранить значения минимумов строк и максимумов столбцов соответственно.

#include <stdio.h>

int n, m, a[750][750], min[750], max[750], i , j, count = 0;

int main(){

freopen("input.txt", "r", stdin);

freopen("output.txt", "w", stdout);

scanf("%d%d", &n, &m);

for(i = 0; i < n; i++) min[i] = 1000;

for(i = 0; i < m; i++) max[i] = -1000;

for(i = 0; i < n; i++)

     for(j = 0; j < m; j++){

           scanf("%d", &a[i][j]);

           if(a[i][j] < min[i]) min[i] = a[i][j];

           if(a[i][j] > max[j]) max[j] = a[i][j];

     }

for(i = 0; i < n; i++)

     for(j = 0; j < m; j++)

           count += a[i][j]==min[i] && a[i][j]==max[j];

printf("%d", count);      

}

Задача №112.  Фермерское поле

Некий фермер имеет земельный участок размером N×M м² (N – с запада на восток, M – с севера на юг). Фермер использовал автоматическую сеялку, которая за один рабочий день может засеять зерном прямоугольный участок поля. В программе для сеялки каждая точка на поле задаётся парой координат (x, y) –отступом от западного и от северного края поля соответственно. Прямоугольник задаётся парой вершин – северо-западной и юго-восточной.

Во время программирования сеялки была допущена ошибка, в результате которой некоторые части поля засевались более одного раза, а некоторые не засевались вообще. Помогите фермеру определить общую площадь засеянной части поля.

Входные данные

В первой строке 3 целых неотрицательных числа через пробел N, M, K. N и M – размеры поля, не превышающие 500, K – количество дней работы сеялки, не превышающее 100.

Kследующих строк содержат по 4 целых неотрицательных числа x1, y1, x2, y2, записанных через пробел.

Выходные данные

Одно число – суммарная площадь засеянной части поля.

Пример

Ввод	Вывод
6  5  4 0  0  4  2 3  1  5  4 1  3  6  5 1  1  2  4	22

Решение

Ключом к решению задачи является то, что все числа в задаче – целые, а размер поля ограничен. Для каждого участка поля размером 1×1 будем считать 1, если он засеян и 0, если не засеян. Таким образом, данные о поле представляют собой матрицу, в которой нужно найти сумму её элементов.

#include <iostream>

#define SIZE 500

int main(){

int a[SIZE][SIZE] = {0,}, n, m, k, x1, x2, y1, y2, s = 0;

std::cin >> n >> m >> k;

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

   std::cin >> x1 >> y1 >> x2 >> y2;

   for(int x = x1; x < x2; x++)

       for(int y = y1; y < y2; y++)

           a[x][y] = 1;

}

for(int x = 0; x < n; x++)

   for(int y = 0; y < m; y++)

       s += a[x][y];

std::cout << s;

}

Задача №113.  Спираль (acmp.ru)

(Время: 1 сек. Память: 16 Мб)

Требуется вывести квадрат, состоящий из N×N клеток, заполненных числами от 1 до N² по спирали (см. примеры).

Входные данные

Одно целое число N – размер квадратной матрицы (2 ≤ N ≤ 100).

Выходные данные

Выведите матрицу, заполненную числами от 1 до N² по спирали, при этом между числами может быть любое количество пробелов. Не допускается начинать спираль в ином, кроме верхнего левого, углу, закручивать спираль против часовой стрелки или изнутри наружу.

Пример

№	Ввод	Вывод
1	3	1  2  3 8  9  4 7  6  5
2	4	1 2 3 4 12 13 14 5 11 16 15 6 10    9   8 7
3	5	1   2 3 4 5 16  17  18  19 6 15  24  25  20 7 14  23 22  21 8 13  12  11  10 9

Решение

При заполнении матрицы воспользуемся вектором {dx, dy}, который будет определять координаты следующей ячейки при перемещении. Каждый раз будем поворачивать направо, если натолкнёмся на выход за край матрицы или на уже заполненную ячейку.

#include <iostream>

int n, a[100][100]={0,}, x = 0, y = 0, dx = 1, dy = 0;

 

bool next(){              // следующая ячейка доступна?

if(x+dx<0 || x+dx>=n || y+dy<0 || y+dy>=n)

   return false;

return !a[y+dy][x+dx];

}

 

void rotate(){            // поворот вправо

int tmp = -dy;

dy = dx;

dx = tmp;

}

 

int main(){

std::cin >> n;

for(int k=1; k<= n*n; k++){ // заполнение матрицы

  a[y][x] = k;       // устанавливаем значение в ячейку

  if(!next()) rotate(); // если идти прямо нельзя - поворот

  x += dx;           // переходим в следующую ячейку

  y += dy;

}

for(y = 0; y < n; y++){ // вывод матрицы

    for(x = 0; x < n; x++)

      std::cout << a[y][x] << ' ';

  std::cout << '\n';

}

}

Задача №114.  Медианная фильтрация

Медианная фильтрация данных – одна из интереснейших задач информатики по обработке сигналов, подверженных воздействию шума[24]. Этот метод позволяет уменьшить последствия от искажения цифровых сигналов.

Например, глубоководный аппарат передаёт сведения об уровнях океанского дна. Периодически в сигнале появляются искажения (допустим, данные передаются без точки, отделяющей целую часть от дробной и т.д.). Можно ли по таким данным составить представление об объекте, более соответствующее действительности?

Часто медианная фильтрация применяетсяпри обработке цифровых фотографий.

Рис. 18. Результат применения медианных фильтров к зашумленному изображению.