1458. Военные учения
В каждой клетке плаца размером n * n
находится солдат. Каждый солдат может находиться в одном из двух положений:
“упор лежа” или “строевая стойка”. Генерал дает команды, называя номер клетки (i, j).
По его команде все солдаты, находящиеся в i
- ой горизонтали и j - ой вертикали,
меняют положение (таких солдат всегда будет в точности 2*n – 1). Необходимо найти такую наименьшую последовательность
команд, после выполнения которой все солдаты примут одинаковое положение (в
армии все должно быть единообразно).
Вход. Первая
строка содержит размер плаца – четное число n
(2 £ n £ 1000). Следующие n строк содержат по n символов – начальное положение солдат на плацу. Символ
"W" соответствует положению “упор лёжа”, а символ "B" -
положению “строевая стойка”.
Выход. Первая строка содержит
наименьшее количество команд k, через
которое все солдаты будут находиться в одинаковом положении. Следующие k строк содержат команды генерала,
ведущие к требуемому расположению солдат. Если существует несколько последовательностей
команд, ведущих к требуемому расположению, то вывести одну из них.
4
WBWB
BWWW
WWBW
WBWB
2
2 3
3 1
математика
Поскольку n четно, то задача всегда имеет решение. Для того чтобы поменять
положение только одного солдата в позиции (i,
j), необходимо выполнить следующую
последовательность команд: (i, 1), (i, 2), …, (i, j), …, (i, n),
(1, j), (2, j), (i – 1, j), (i
+ 1, j),
…, (n, j). То есть генерал должен назвать все клетки, находящиеся в i – ой строке и j – ом столбце, по одному разу. Очевидно, что генералу в искомой
последовательности нет смысла называть одну клетку дважды, так как дважды
выполненная одна и та же команда не меняет состояние солдат.
Преобразовываем всех солдат в
положение “строевая стойка”, меняя положения всех солдат, которым отвечает
символ “W”. Затем преобразовываем всех солдат в положение “упор лежа”, меняя
положения всех солдат, которым отвечает символ “B”. Функция HowManyMoves(c) находит наименьшее число команд,
которое требуется для преобразования всех солдат из положения c в противоположное. Находим, в какое из
двух положений следует преобразовывать всех солдат чтобы выполнить меньшее
количество команд.
При выполнении команды (i, j)
значение temp[i][j] меняем на противоположное (0 на 1, 1 на 0).
Размеры рабочих массивов
устанавливаем в MAX = 1001, так как n
£ 1000. Состояние солдат на плацу
храним в символьном массиве m. Факт изменения только одного положения солдата в
ячейке (i, j) приведенным выше набором команд будем фиксировать в массивах
row[MAX], col[MAX] и temp[MAX][MAX], меняя значения row[i], col[j] и temp[i][j]
на противоположные (0 или 1). В результате row[i] = 1, если требуется дать команды (i, 1), (i, 2), …, (i, n).
col[j] = 1, если требуется дать
команды (1, j), (2, j), …, (n, j). temp[i][j]
= 1, если требуется дать команду (i, j). Но поскольку при установке row[i] и col[j] на противоположные, дается дважды команда (i, j), то в ячейке temp[i][j]
мы отмечаем, что следует дать еще команду (i,
j).
#define MAX 1001
char m[MAX][MAX];
int row[MAX],col[MAX],temp[MAX][MAX];
int i,j,moves,n;
int HowManyMoves(char c)
{
int i,j,k;
Обнуляем рабочие массивы.
memset(temp,0,sizeof(temp));
memset(row,0,sizeof(row));
memset(col,0,sizeof(col));
Проходим по плацу. Для каждого
символа c в ячейке (i, j)
меняем на противоположное значения row[i],
col[j] и temp[i][j].
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if (m[i][j] == c)
{
row[i] = 1 -
row[i]; col[j] = 1 - col[j];
temp[i][j] = 1 -
temp[i][j];
}
Для каждого row[i] = 1 выполняем команды (i, 1), (i, 2), …, (i, n). Для каждого col[j] = 1 выполняем команды (1, j),
(2, j), …, (n, j).
for(i=0;i<n;i++)
{
if (row[i])
for(j=0;j<n;j++) temp[i][j] = 1 - temp[i][j];
if (col[i])
for(j=0;j<n;j++) temp[j][i] = 1 - temp[j][i];
}
Вычисляем количество 1 в массиве
temp. Оно равно наименьшему количеству команд, которое надо выполнить для
преобразования всех солдат в состояние, отличное от c.
for(k=i=0;i<n;i++)
for(j=0;j<n;j++)
if (temp[i][j])
k++;
return k;
}
Основной цикл программы. Читаем
размер плаца и начальное расположение солдат на нем в массив m.
scanf("%d",&n);
for(i=0;i<n;i++) scanf("%s",m[i]);
Преобразовываем всех солдат в положение
“упор лежа”. Затем преобразовываем их в положение “строевая стойка”. Смотрим,
какое из этих преобразований требует выполнения меньшего количества команд, то
и запоминаем.
moves = HowManyMoves('W');
i = HowManyMoves('B');
if (moves < i) moves = HowManyMoves('W'); else moves = i;
Выводим количество команд moves и сами команды. Если temp[i][j]
= 1, то генералу следует дать команду (i,
j).
printf("%d\n",moves);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if (temp[i][j])
printf("%d %d\n",i+1,j+1);