10946. Вы хотите это заполнить?
Имеется поле
прямоугольного вида, в котором находятся ямки. Ямки следует заполнить едой
начиная с наибольшей. Необходимо установить последовательность наполнения ямок.
Вход.
Первая строка каждого теста содержит размеры поля x и y (x,
y < 50). Далее следует x строк по y символов в каждой,
описывающих состояние поля. Ямки обозначаются заглавными буквами латинского
алфавита (от A до Z), ровная земля – символом ‘.’. Последний тест содержит x
= y = 0 и не обрабатывается.
Выход. Для каждого теста вывести его
номер и последовательность ямок (имя и размер), согласно которой будет
происходить их наполнение пищей. Ямки выводить в порядке уменьшения их размера.
Ямки с одинаковым размером выводить в алфавитном порядке их имен.
5 5
..AAA
E.BBB
..AA.
CC.DD
CC.D.
5 5
..AAA
E.BBB
..AA.
CC.DD
CC.D.
0 0
Problem 1:
C 4
A 3
B 3
D 3
A 2
E 1
Problem 2:
C 4
A 3
B 3
D 3
A 2
E 1
обработка текста, заполнение
Просматриваем поле
сверху вниз и слева направо. Для каждой буквы запускаем процедуру dfs, которая
проходит по всем клеткам текущей ямки и заметает ямку, заполняя ее землей
(символами ‘.’). Запоминаем имя ямки (соответствующий ей символ) и ее размер.
Когда все ямки просмотрены, сортируем их по убыванию размера; ямки с одинаковым
размером сортируем по возрастанию имен.
Состояние поля будем
хранить в символьном массиве s. Информацию о каждой ямке (ее размер и
имя) заносим в вектор v. В переменной p будем хранить номер
текущего теста.
char s[50][50], ch;
int p;
vector<pair<int,char> > v;
Читаем размеры поля в переменные x
и y, состояние поля – в массив s.
while(scanf("%d
%d\n",&x,&y),x+y > 0)
{
v.clear();
for(i = 0; i < x; i++) gets(s[i]);
Просматриваем поле сверху вниз и
слева направо (производим заметание). Для каждой встретившейся ямки (символа,
отличного от ‘.’) вызываем функцию dfs, которая вычисляет ее размер и заполняет
землей (символами ‘.’). В символьной переменной ch храним имя ямки.
Размер ямки и ее имя заносим в вектор v.
for(i = 0; i
< x; i++)
for(j = 0; j
< y; j++)
{
if
(s[i][j]!='.')
{
ch = s[i][j];
temp = dfs(i,j);
v.push_back(make_pair(temp,ch));
}
}
Сортируем ямки по
убыванию размера и по возрастанию их имен.
sort(v.begin(),v.end(),comp);
Выводим номер теста p и
последовательность наполнения ямок пищей.
printf("Problem
%d:\n",++p);
for(i = 0; i
< v.size(); i++)
printf("%c
%d\n",v[i].second,v[i].first);
}
Функция сортировки
comp имеет вид:
int comp(pair<int,char> p1, pair<int,char> p2)
{
if (p1.first
> p2.first) return 1; else
if ((p1.first
== p2.first) && (p1.second < p2.second)) return
1;
return 0;
}
Функция dfs вычисляет размер ямки
с именем ch и заполняет ее землей (символами ‘.’).
int dfs(int
i, int j)
{
if ((s[i][j]
!= ch) || (i < 0) || (i >= x) || (j < 0) || (j >= y))
return 0;
s[i][j] = '.';
return 1 +
dfs(i-1,j) + dfs(i+1,j) + dfs(i,j-1) + dfs(i,j+1);
}