Определить оптимальные координаты вырубки леса

Петя не мечтает быть программистом - он хочет стать миллионером. И не где-нибудь в далеком будущем, а уже в этом году. Для воплощения своей мечты Петя организовал фирму, которая под Новый год будет заниматься поставкой новогодних елок. Поскольку миллион надо заработать уже в этом году, Петя решил обойтись без посредников. Бизнес-план вышел удивительно прост: сам рублю, сам доставляю и сам продаю. Петя смело взялся за дело, но когда получил соглашение на вырубку елок, то задумался. За один раз ему разрешили вывозить ровно K (0 <= K <= 10000) елок и партия Зеленых добилась определенных ограничений на вырубку: елки можно рубить только двигаясь на восток или на юг, начинать вырубку следует в одном углу и заканчивать в любом другом. Участки имеют форму прямоугольника со сторонами N, M (1 <= N, M <= 100), стороны которого были ориентированы строго на запад, восток, север и юг. Петя сразу же заметил, что обеспечить себе хороший результат вырубки можно только тогда, когда начинаешь рубить с северо-западного угла и заканчиваешь в юго-восточном. «Зеленые» хорошо подумали над тем, чтобы выполнить соглашение по вырубке ему было сложно. Петя это увидел и пожалел, что не стал сначала программистом. Помогите Петя правильно провести вырубку и стать миллионером, или сообщите, что на этом участке лучше не рубить.
Входные данные: В первой строке входного файла даны три целых числа N, M, K, разделенных пробелами. Дальше в N строках содержится по M символов «.» - Это свободное место, а «#» - обозначает место нахождения елки.
Выходные данные: В выходной файл в случае наличия правильного варианта вырубки вывести последовательность координат, которые выводить по одной в каждой строке. Первая координата всегда (1,1), последняя - (N, M). В противном случае вывести сообщение «To not cut!»
Пример 1:
Вход:
4 4 3
....
#...
###.
####
Выход:
1 1
2 1
2 2
2 3
3 3
3 4
4 4
Пример 2:
Вход:
3 4 1
#...
..#.
#.##
Выход:
To not cut!
Я реализовал задачу, она работает вроде как правильно, но проблема в том, что она работает слишком долго для примеров, когда n и m большие числа:
Подскажите как еще можно решить

0