문제<\/h2>
Barrett has discovered an ancient maze under his house. It has the shape of an $n<\/mi>\times<\/mo>m<\/mi><\/mrow>n \times m<\/math><\/span><\/span> n<\/span> <\/span> \times<\/span> <\/span><\/span> <\/span> m<\/span><\/span><\/span><\/span> grid, where some cells are empty, while others are blocked. It is possible to walk from one empty cell to another if they share a side. Two of the empty cells are an entrance and an exit, and it is possible to reach one from the other by walking through empty cells.<\/p> Barrett wants to isolate his house by building a wall inside the maze, blocking some cells to make the exit unreachable from the entrance. The wall should be straight and oriented either vertically or horizontally. Specifically, a wall of length k<\/mi><\/mrow>k<\/math><\/span><\/span> k<\/span><\/span><\/span><\/span> will block a consecutive row or column of exactly k<\/mi><\/mrow>k<\/math><\/span><\/span> k<\/span><\/span><\/span><\/span> cells. The wall may not contain the entrance, the exit, or any already blocked cells.<\/p> Help Barrett determine the minimum possible length of the wall.<\/p> 입력<\/h2> Each test contains multiple test cases. The first line contains the number of test cases t<\/mi><\/mrow>t<\/math><\/span><\/span> t<\/span><\/span><\/span><\/span> (1<\/mn>\leq<\/mo>$

Brick in the Wall, Part 2