fun main() { val (h, w) = readln().split(" ").map { it.toInt() } val block = System.`in`.bufferedReader().lineSequence().take(h) .map { l -> l.map { it == '#' }.toBooleanArray() } .toList() // a 90 degrees turned block for convinience val turnedBlock = Array(w) { y -> BooleanArray(h) { x -> block[h - x - 1][y] } }.toList() // types that we can place // ## ## ## ### ### // # ## # # # # // Types that we can't place // ### ##### // #.# #...# // ### ##.## // for the 4 directions of the block // 1. check if the top row is fully filled in desired rotation // 2. Construct a result with a of 2 wider with a hole in the middle of size hxw // 3. fill the hole with the open spaces of the block in correct oritation from bottom to top // 4. check that once you stop filling you don't start filling again, else break of attempt // 5. print out result // Worst case for this approach, fully filled block with a hole in the middle // time complexity O(4hw) // current direction if (block.topFull(0)) { val layout = Array(h) { BooleanArray(w + 2) { it == 0 || it == w + 1 } } // fill in, column by column bottom to top, once filling start, no more blanks may be printed var valid = true (0 until w).forEach fill@{ x -> var filling = false (h - 1 downTo 0).forEach { y -> if (block[y][x] && !filling) filling = true if (!block[y][x] && filling) { valid = false return@fill } layout[y][x + 1] = !block[y][x] } } if (valid) { println("$h ${w + 2}") println(layout.joinToString("\n") { line -> line.joinToString(separator = "") { if (it) "#" else "." } }) return } } // 90 degrees if (turnedBlock.topFull(0)) { var valid = true; val layout = Array(w) { BooleanArray(h + 2) { it == 0 || it == h + 1 } } (0 until h).forEach fill@{ x -> var filling = false (w - 1 downTo 0).forEach { y -> if (turnedBlock[y][x] && !filling) filling = true if (!turnedBlock[y][x] && filling) { valid = false return@fill } layout[y][x + 1] = !turnedBlock[y][x] } } if (valid) { println("$w ${h + 2}") println(layout.joinToString("\n") { line -> line.joinToString(separator = "") { if (it) "#" else "." } }) return } } // 180 degrees if (block.topFull(h - 1)) { var valid = true val layout = Array(h) { BooleanArray(w + 2) { it == 0 || it == w + 1 } } (w - 1 downTo 0).forEach fill@{ x -> var filling = false (0 until h).forEach { y -> if (block[y][x] && !filling) filling = true if (!block[y][x] && filling) { valid = false return@fill } layout[h - y - 1][w - x] = !block[y][x] } } if (valid) { println("$h ${w + 2}") println(layout.joinToString("\n") { line -> line.joinToString(separator = "") { if (it) "#" else "." } }) return } } // 270 degrees if (turnedBlock.topFull(w - 1)) { var valid = true val layout = Array(w) { BooleanArray(h + 2) { it == 0 || it == h + 1 } } (h - 1 downTo 0).forEach fill@{ x -> var filling = false (0 until w).forEach { y -> if (turnedBlock[y][x] && !filling) filling = true if (!turnedBlock[y][x] && filling) { valid = false return@fill } layout[w - y - 1][h - x] = !turnedBlock[y][x] } } if (valid) { println("$w ${h + 2}") println(layout.joinToString("\n") { line -> line.joinToString(separator = "") { if (it) "#" else "." } }) return } } println("impossible") } fun List.topFull(y: Int) = get(y).all { it }