Рассмотрим конвейер, представляющий собой сетку, состоящую из \(n\) строк и \(m\) столбцов. Ячейка в \(i\)-й строке сверху и в \(j\)-м слева столбце обозначается как \((i,j)\).
Каждой ячейке, кроме \((n,m)\), назначено направление R (вправо) или D (вниз). Если ячейке \((i,j)\) назначено направление R, любой багаж в ней переместится в ячейку \((i,j+1)\). Аналогично, если ячейке \((i,j)\) назначено D, любой багаж в ней переместится в ячейку \((i+1,j)\). Если в любой момент времени багаж выходит за пределы сетки, он считается утерянным.
В ячейке \((n,m)\) есть стойка, где подбирается весь багаж. Конвейер называется работоспособным тогда и только тогда, когда любой багаж достигнет стойки, независимо от того, в какую ячейку он изначально помещен. Более формально, для каждой ячейки \((i,j)\) любой багаж, помещенный в эту ячейку, должен в итоге оказаться в ячейке \((n,m)\).
Может случиться такое, что это условие изначально не выполняется; вам, однако, разрешено изменять направления некоторых ячеек для обеспечения работоспособности конвейера. Пожалуйста, определите минимальное количество ячеек, направления в которых вы должны изменить.
Обратите внимание, что всегда можно сделать любой конвейер работоспособным, изменив направления набора ячеек.
Примечание
В первом случае достаточно просто изменить направление \((2,3)\) на D.
Вы можете проверить работоспособность полученного конвейера. Например, если мы поместим багаж в \((2,2)\), он сначала переместится в \((3,2)\), а затем в \((3,3)\).
Во втором случае у нас нет другого выбора, кроме как изменить первые \(3\) ячейки с D на R, сделав сетку равной RRRC.