题目描述
小铭今天编程实现了迷宫找路径的算法:在一个 n 行、m 列的迷宫中,有代表空地的格子 (用 点 “.” 表示) 和代表障碍的格子 (用 “#” 表示)。迷宫中的人可以在空地上移动,但不能移动到障碍上。每一步,迷宫中的人可以向上、下、左、右四个方向移动一格。小铭的程序能求出从左 上角到右下角最少移动的步数。
小铭对他的程序并不是很有信心,因此希望你用程序生成一个 n 行、m 列的迷宫,且从左上角到右下角最少移动步数恰好是 k,帮助他测试程序是否正确。
输入格式
输入一行三个整数 n,m和k。
输出格式
输出 n 行,每行 m 个字符 (“.” 或 “#”),表示迷宫。左上角和右下角必须是空白 (“.”)。输入保证存在最少移动步数恰好是 k 的迷宫。
满足条件的迷宫可能很多,输出任意一个即可。
样例数据
input1
4 4 6
output1
....
#...
##..
###.
input2
3 5 10
output2
.#...
.#.#.
...#.
数据范围与提示
对于60% 的数据,满足 n,m≤8;
对于 100% 的数据,满足 n,m≤16