Задача: "Сапер" с подсказками
На весенних каникулах Оля долго обдумывала свое поведение и решила в четвертой четверти заниматься учебой побольше. Но уже первый урок биологии в новой четверти уничтожил все Олины благие намерения. Оле скучно, просто невыносимо скучно. От нечего делать она начала играть на своем телефоне в известную игру «Сапер».
На всякий случай напомним, в чем заключается эта игра. Игра происходит на поле размером N × M клеток, некоторые из которых «заминированы». Целью игры является открытие всех клеток, не содержащих мины.
Игрок открывает клетки, стараясь не открыть клетку с миной. Открыв клетку с миной, он проигрывает. Если под открытой ячейкой мины нет, то в ней появляется число, показывающее, сколько ячеек, соседствующих с только что открытой, «заминировано». Клетки считаются соседствующими, если у них есть общая сторона или общая вершина. Клетки, которые игрок считает «заминированными», можно пометить флажком, чтобы случайно не открыть их.
Оля играет в версию «Сапера» со встроенными подсказками. Одна из подсказок, «Показать ошибки», работает следующим образом. Если по соседству с клеткой, в которой записано некоторое число, находится больше флажков, чем может соседствовать с этой клеткой (то есть больше флажков, чем число, записанное в клетке), все флажки вокруг этой клетки подсвечиваются желтым цветом. Другие ошибки эта подсказка находить не умеет, иначе играть было бы совсем не интересно.
Ваша задача — по текущему состоянию игрового поля определить, какие флажки окажутся подсвечены желтым после запуска подсказки.
Входные данные
В первой строке содержатся два числа N и M, разделенные пробелами — высота и ширина таблицы соответственно (1 ≤ N ≤ 15, 1 ≤ M ≤ 15). В следующих N строчках содержится по M символов в каждой. Эти строчки задают игровое поле. Используются следующие обозначения:
F — флажок;
* — закрытая клетка;
Цифра от 0 до 8 — открытая клетка. Сама цифра обозначает, сколько суммарно мин находится в клетках, соседствующих с данной.
Выходные данные
В первой строке выведите количество флажков, которые окажутся подсвечены желтым, а в следующих N строчках выведите для каждого такого флажка его координаты — номер строки, а затем номер столбца, в котором стоит флажок. Флажки можно выводить в любом порядке.
Если подсвеченных флажков не будет, выведите единственное число 0
Примеры
| № |
Входные данные |
Выходные данные |
Пояснения |
| 1 |
2 3
FFF
*2* |
3
1 2
1 3
1 1 |
В тесте в клетке с координатами (2, 2) записано число 2, а касается она трех флажков, что больше двух. Значит, все эти три флажка будут подсвечены. |
Ваш ответ: