Матч 200, Гравитационная бомба (GravityBomb)

Дивизион 2, Уровень 2

Имеется вертикально стоящая прямоугольная сетка, в которой находятся блоки размера 1*1, падающие вниз. Если в какой-нибудь ряд окажется полностью заполненным блоками, то этот ряд исчезает, а все выше стоящие блоки опускаются вниз на один ряд.

Известны размеры сетки и начальное расположение блоков в ней. При выполнении операции “Бомба” все блоки падают вниз, заполняя свободные ячейки сетки под собой. Процесс продолжается, пока хотя бы один блок может упасть вниз. При этом если какая-нибудь строка полностью заполнится блоками, то она удаляется, и процесс падения блоков продолжается.

В задаче необходимо найти состояние блоков после выполнения операции “Бомба”.

Класс: GravityBomb

Метод: vector<string> aftermath(vector<string> board)

Ограничения: массив board содержит от 1 до 50 строк, каждая строка board[i] содержит от 1 до 50 символов, все строки массива board имеют равную длину, каждый символ board[i][j] содержит ‘X’ или ‘.’.

Вход. Массив строк board содержит начальное состояние блоков в сетке. Первая строка массива представляет собой описание верхнего ряда сетки, последняя строка описывает нижний ряд сетки.

Выход. Массив строк, описывающий состояние блоков в сетке после выполнения операции “Бомба”.

Пример входа

board

{"..X",

"X.X",

".X."}

{"XXXXXX",

"......",

"......"}

{"XX.XX....XX"}

Пример выхода

{"...", "...", "..X"}

{"......", "......", "......"}

{"XX.XX....XX"}

РЕШЕНИЕ

математика

В ячейках массива m подсчитаем количество блоков, которое содержится в каждом столбце сетки: m[i] содержит число блоков в столбце i (1 £ i £ width, где width – ширина сетки). Когда все блоки упадут вниз, число полностью заполненных рядов будет равно наименьшему элементу массива m. Вычитаем это значение изо всех ячеек m[i]. Далее строим сетку, заполняя ее снизу вверх согласно правилу: если m[i] = k, то в i - ой колонке должно находиться k блоков, лежащих друг на друге, причем самый нижний блок должен находиться в нижнем ряду сетки.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <string>

#include <memory>

using namespace std;

class GravityBomb

{

public:

vector<string> aftermath(vector<string> board)

{

int min = 2000000000, i, j;

int m[50], len = board.size(), width = board[0].size();

memset(m,0,sizeof(m));

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

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

if (board[i][j] == 'X') board[i][j] = '.', m[j]++;

for(i = 0; i < width; i++) if (m[i] < min) min = m[i];

for(i = 0; i < width; i++) m[i] -= min;

for(i = len - 1; i >= 0; i--)

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

if (m[j] > 0) board[i][j] = 'X', m[j]--;

return board;

}

};