408760: GYM103295 H Land Bridge

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

H. Land Bridgetime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

An evil supervillain has stranded some innocent civilians in an archipelago! Luckily, the legendary flying superhero Agamemnon has come to save the day!

The archipelago can be mapped in an $$$N \times N$$$ grid. The civilians are stuck at location $$$(1,1)$$$ and Agamemnon has spotted a helipad at $$$(N, N)$$$.

Agamemnon has a special ability: he can build land between these islands, effectively replacing a square of water with land. By connecting the civilians to the helipad (they can only travel in the $$$4$$$ cardinal directions), he hopes to quickly evacuate them.

However, as is common with many omnipotent individuals, he has grown incredibly lazy and despite wanting to help, wants to expend minimal effort, so he can resume feeding his addiction to competitive programming.

Given an $$$N \times N$$$ map of the region and which cells are land and water, help Agamemnon determine the smallest amount of land he must create to effectively evacuate the civilians.

Input

The first line contains a single number, $$$1 \leq N \leq 500$$$. The next $$$N$$$ lines display the grid, containing $$$N$$$ digits each, either $$$0$$$ for water or $$$1$$$ for land.

Output

A single integer, the smallest amount of land needed to evacuate the civilians.

ExampleInput
5
11010
00000
01011
01000
01101
Output
2
Note

The civilians $$$(1,1)$$$ and helipad $$$(N, N)$$$ will always be on land.

加入题单

上一题 下一题 算法标签: