| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 39 | 12 | 11 | 31.429% |
Университеты Татарстана являются ведущими центрами по образовательной робототехнике. Для популяризации этого направления школьникам было предложено провести эксперимент по выживанию роботов в ограниченном пространстве.
Эксперимент проходит на прямоугольном поле размером $n \times m$ клеток. В начале эксперимента в заданных клетках размещается по одному неактивированному роботу. По команде <<Старт>> запускается таймер, который подаёт сигнал в начале каждой секунды. После каждого сигнала таймера, но не позднее чем через $T_{max} = 10^9$ секунд после команды <<Старт>>, разрешается активировать некоторых роботов.
Каждая клетка поля закрашена в один из четырёх цветов, распознаваемых сенсором робота. Цвет обозначает направление движения из данной клетки в соседнюю: на север, юг, восток или запад. В момент сигнала таймера каждый активированный робот перемещается в соседнюю клетку в направлении, соответствующем цвету клетки, в которой он находится. Все активированные роботы перемещаются одновременно. Цвета клеток поля выбраны так, что при перемещении никакой робот не может выйти за пределы поля.
Во избежание повреждений запрещается активировать роботов таким образом, что это приведёт к их столкновению. Столкновением называется ситуация, когда два или более активированных роботов оказываются в одной клетке поля. Если происходит столкновение, то эксперимент считается неуспешным. При этом перемещение роботов из соседних клеток навстречу друг другу, в результате которого они меняются местами, к столкновению не приводит.
Эксперимент считается завершённым успешно, если все активированные роботы могут продолжать движение без столкновений по полю сколь угодно долго. Результатом эксперимента является количество активированных роботов.
Требуется написать программу, которая поможет школьникам по описанию поля и клеток, где исходно располагаются неактивированные роботы, определить максимально возможный результат эксперимента и, если потребуется, каких именно роботов и в какие моменты времени следует активировать для достижения такого результата.
В первой строке входных данных записаны целые числа $n,ドル $m$ и $g,ドル где $n$ и $m$ --- размеры поля с севера на юг и с запада на восток соответственно (1ドル \le n, m \le 1000$), а $g$ --- признак, равный 1ドル$ или 0ドル,ドル обозначающий необходимость определения клеток и моментов времени для активации роботов.
Последующие $n$ строк по $m$ символов в каждой описывают цвета клеток поля и разрешение на активацию робота в них. Цвет поля задаётся английской буквой, соответствующей направлению движения: <<N>> или <<n>> --- север, <<S>> или <<s>> --- юг, <<E>> или <<e>> --- восток и <<W>> или <<w>> --- запад.
Клетки, в которых исходно размещены неактивированные роботы, обозначены заглавными буквами, а клетки, в которых исходно робота нет --- строчными.
В первой строке выходных данных выведите одно число $k$ --- максимально возможный результат эксперимента. Для входных данных, в которых значение $g$ равно 1, в каждой из последующих $k$ строк выведите три целых числа $r,ドル $c$ и $t$: номера строки и столбца, описывающие клетку для активации робота, и момент времени для его активации соответственно (1ドル \leq r \leq n$; 1ドル \leq c \leq m$; 1ドル \leq t \leq 10^9$). Строки нумеруются от 1 до $n$ сверху вниз (с севера на юг), а столбцы --- от 1 до $m$ слева направо (с запада на восток).
Если стратегий активации роботов, приводящих к максимальному результату несколько, то выведите любую из них.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 11 | 1ドル \leq n, m \le 10,ドル $g = 0,ドル в каждой клетке исходно находится робот |
| 2 | 13 | 1ドル \leq n, m \le 100,ドル $g = 0,ドル в каждой клетке исходно находится робот |
| 3 | 13 | 1ドル \leq n, m \le 100,ドル $g = 0$ |
| 4 | 23 | 1ドル \leq n, m \le 100,ドル $g = 1$ |
| 5 | 17 | 1ドル \leq n, m \le 1000,ドル $g = 0$ |
| 6 | 23 | 1ドル \leq n, m \le 1000,ドル $g = 1$ |
3 4 0 SSSS EESW ENWW
4
3 4 1 SSSS EeSW ENwW
4 2 3 2 3 2 1 3 4 1 2 1 2
4 4 1 essS Eess Snww EeWN
5 1 4 9 2 1 4 4 3 3 4 1 2 4 4 7
В первом примере можно активировать любых четырёх роботов, выбрав для этого подходящие моменты времени. Например, роботы, находящиеся в клетках (1, 1) и (3, 1) не могут быть активированы одновременно. Указывать, какие именно роботы должны быть активированы и в какие моменты в времени, в данном тесте не требуется.
Во втором примере приведённый ответ не является единственным.
В третьем примере активированные в клетках (4, 1) и (4, 3) роботы могут перемещаться между клетками (4, 2) и (4, 3) сколько угодно раз, не сталкиваясь при этом.