408760: GYM103295 H Land Bridge

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.

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.

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

5
11010
00000
01011
01000
01101

2

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