Left labyrinths

TimeLimit:1000MS MemoryLimit:10000K

64-bit integer IO format:%lld

未提交 | 登录后收藏

Problem Description

"The instructions to turn always to the left reminded me that such was the common procedure for discovering the central courtyard of certain labyrinths."
in The garden of forking paths by Jorge Luis Borges.
A fellow librarian has exhumed in the Library of Babel a vast catalogue of labyrinths. It is our duty to classify them all and we count on your assistance. The plans of the labyrinths are already digitized and we need you to write a program to decide if the central courtyard of a given labyrinth can be reached following the simple procedure of always turning left at any intersection, and thus be called a left labyrinth.

The digitalization process reduces the plan of a labyrinth to a grid of cells, being each cell either a block of wall or just floor. Walls are sequences of contiguous blocks, forming either horizontal or vertical corridors between them. Each labyrinth has a single entrance, a hole in its exterior walls, and a single central courtyard. The courtyard differs from the corridors in the shape: a floor cell in a corridor has at least 2 block of wall on each side. You can assume that each plan has a single labyrinth and its outside walls can be contoured within the plan.

Input

The first two input lines are the integers, smaller than 100,

n - the number of lines in the map, and

m - the number of characters per line in the map.

The following n lines, each with m characters, have only two valid character values:

# - (sharp) representing a block of a wall;

. - (dot) representing part of the floor.

Output

Your program must write either YES if the given labyrinth is a left labyrinth or NO otherwise

SampleInput

30
50
..................................................
..................................................
..................................................
.....##############..............############.....
.....#.........#..#..............#..........#.....
.....#.#######.#.##..............#.########.#.....
.....#.#.....#....#..............#.#......#.#.....
.....#.#.#####.####..............#.#.####.#.#.....
.....#.#.....#...#################.#.##.#...#.....
.....#.#####.###........................#.#.#.....
.....#.........#.###############.#.##########.....
.....#########.#.#.#...........#.#..#.............
.............#.#.#.#...........###.##.............
.............#.#.#.#...........#....#.............
.............#.#...#...........#.##.#.............
.............#######...........#.##.#.............
.............#.................#.#..#.............
.............#.#################.####.............
.....#########...#.................##########.....
.....#.........###.#.#.##########.#######.#.#.....
.....#.#########.....#.#..........#.....#.#.#.....
.....#.#.........#####.##########.#.###.#.#.#.....
.....#.######.#####...........#.#.#.#.#.#.#.#.....
.....#......#.....#...........#.....#.#.#.#.#.....
.....#.##########.#...........#####.#.#.#.#.#.....
.....#............#...........#...........#.#.....
.....##############...........###############.....
..................................................
..................................................
..................................................

SampleOutput

YES

Submit

题目统计信息详细


总AC数	1
通过人数	1
尝试人数	3
总提交量	5
AC率	20.00%

标签——1812

name	rating
基础	200

AC该题后可以添加标签
贴完标签可以获得20ACB。
并且可以获得本题所有提交代码查看权限。
点击标题可以显示标签。
如果你还没认真思考过这题，请不要查看标签
如果您已经通过了该题，请务为该题贴上标签

出处

【15级寒假作业】大概够做一学期的狗狗40题

Left labyrinths

T^T Online Judge